如何获取表示矩形的数组中与特定索引对角线上的元素

Question

考虑一个长度始终为两个数字的乘积的数组。对于下面的数组，l是4，w是5。

同时还有一个给定的索引。我想要获取包含通过该特定索引的对角线上的元素的两个数组。

[
    0,  1,  2,  3,  4
    5,  6,  7,  8,  9
    10, 11, 12, 13, 14
    15, 16, 17, 18, 19
]  

index = 7 => [3, 7, 11, 15] and [1, 7, 13, 19]
index = 16 => [4, 8, 12, 16] and [10, 16]
index = 0 => [0, 6, 12, 18] and [0]

我尝试了以下方法：

let arr = Array(20).fill().map((x,i) => i);

function getDias(arr, l, w, ind){
  let arr1 = [];
  let arr2 = [];
  
  for(let i = 0;i<l;i++){
    arr1.push(arr[ind + (i * w) + i])
    arr1.push(arr[ind - (i * w) - i])
    arr2.push(arr[ind + (i * w) + i])
    arr2.push(arr[ind - (i * w) - i])
  }
  const remove = arr => [...new Set(arr.filter(x => x !== undefined))];
  return [remove(arr1),remove(arr2)];

}
console.log(getDias(arr, 4, 5, 7))

代码存在两个问题。结果中的两个数组都是相同的，并且它们不是有序的。

注意：我不想使用sort()来重新排序数组。同时我也不想遍历所有20个元素。只想获取那条对角线上的元素。

- Maheer Ali

Answer 1

一些数学运算（例如模，整数除法和最小值）可以找到从左到右（LTR）和从右到左（RTL）运行的对角线的起始行和列，节省了迭代向后查找起始点的复杂度。然后，使用那些起始行和列，只需迭代直到数组的高度和宽度超出范围。

let arr = Array(20).fill().map((x, i) => i);

function diagonals(arr, h, w, n) {
  var nRow = Math.floor(n / w);
  var nCol = n % w;

  let LTR = [];
  for (let r = nRow - Math.min(nRow, nCol), c = nCol - Math.min(nRow, nCol); r < h && c < w; r++, c++) LTR.push(arr[r * w + c]);

  let RTL = [];
  for (let r = nRow - Math.min(nRow, w - nCol - 1), c = nCol + Math.min(nRow, w - nCol - 1); r < h && 0 <= c; r++, c--) RTL.push(arr[r * w + c]);

  return [LTR, RTL];
}

样例运行...

diagonals(arr, 4, 5, 7);  // returns ==> [[1, 7, 13, 19], [3, 7, 11, 15]]
diagonals(arr, 4, 5, 15); // returns ==> [[15], [3, 7, 11, 15]]

编辑说明：关于数组值与索引的说明。

另外，需要澄清一点。问题指出：“还有一个给定的索引。我想获取包含通过该特定索引的对角线上元素的两个数组。” 如果寻找的是矩形数组的索引而不是实际值arr，则无需构建arr，随后可以更改function和push语句为...

• function diagonals(h, w, n)
• LTR.push(r * w + c)
• RTL.push(r * w + c)

- Trentium

Answer 2

尝试以下代码。

let arr = Array(20).fill().map((x,i) => i);

function getDias(arr, l, w, ind){
  let arr1 = [];
  let arr2 = [];
  n = l*w;
  lVal = Math.floor(ind/w);
  rVal = ind%w;
  temp1  = lVal;
  temp2  = rVal;
  while(temp1>=0 && temp2>=0){
    val = ((w*temp1) + temp2);
    arr1.unshift(arr[val]);  
    temp1--;
    temp2--;
  }
  temp1  = lVal;
  temp2  = rVal;
  temp1++;
  temp2++;
  while(temp1<l && temp2<w){
    val = ((w*temp1) + temp2);
    arr1.push(arr[val]);  
    temp1++;
    temp2++;
  }

   
  console.log(arr1);
  temp1  = lVal;
  temp2  = rVal;
  while(temp1>=0 && temp2<w){
    val = ((w*temp1) + temp2);
    arr2.unshift(arr[val]);  
    temp1--;
    temp2++;
  }
  
  temp1  = lVal;
  temp2  = rVal;
  temp1++;
  temp2--;
  while(temp1<l && temp2>=0){
    val = ((w*temp1) + temp2);
    arr2.push(arr[val]);  
    temp1++;
    temp2--;
  }

  console.log(arr2);

}
getDias(arr, 4, 5, 7);
getDias(arr, 4, 5, 16);
getDias(arr, 4, 5, 0);

这个想法是计算 l_val 和 r_val。

l_val = index/w
r_val = index%w

现在，arr[l_val][r_val]标记了通过l_val* w+ r_val找到的矩阵中的位置。

接下来有4个步骤:

1) 从arr[l_val][r_val]开始迭代。同时减1直到到达末尾。将其插入array_1（以保持顺序）。

2) 从[l_val][r_val]开始迭代。同时加1直到到达末尾。将其推入array_1。

3) 从arr[l_val][r_val]开始迭代。同时从l_val减1并从r_val加1，直到到达末尾。将其插入array_2（以保持顺序）。

4) 从[l_val][r_val]开始迭代。同时从l_val加1并从r_val减1，直到到达末尾。将其推入array_2。

- Phenomenal One

---

非常感谢您抽出时间。但我不需要如此复杂的代码。我记得我曾经非常简单地完成了这个任务。但不幸的是，我丢失了那段代码... - Maheer Ali

@MaheerAli，您所说的“复杂”，是指代码的行数还是执行时间？因为后者并不太耗时。 - Phenomenal One

代码行数。 - Maheer Ali

Answer 3

let arr = Array(20).fill().map((x, i) => i);

function getDias(arr, l, w, ind) {
  let arr1 = [];
  let arr2 = [];
  let row = parseInt(ind / w);
  let col = ind - row * w;
  diagIteration(arr, row, col, l, w, -1, arr1);
  diagIteration(arr, row, col, l, w, 1, arr2);
  return [arr1, arr2];
}

function diagIteration(arr, row, col, l, w, strategy, result) {
  // find the starting row and col to begin with
  while (row - 1 >= 0 && col + strategy >= 0 && col + strategy < w) {
    row--;
    col += strategy;
  }
  // iterate the diagonal elements and add it in result
  strategy *= -1; // since we need to diagonally the reverse way after getting the base indexes to begin with
  for (; row >= 0 && row < l && col >= 0 && col < w; row++, col += strategy) result.push(arr[row * w + col]);
}

// tests
for (var i = 0; i < arr.length; ++i) {
  console.log(arr[i] + ' =>', getDias(arr, 4, 5, i));
}

我们计算给定索引的行和列。对于任何给定的索引，行将是 `index / width`，列将是 `index - row * width`。

现在，我们找到基本索引并迭代对角线，就像它是一个二维数组一样。任何对角线上的索引都可以计算为 `row * width + column`。我们还进行了额外的检查，以查看我们是否仍在模拟的二维数组范围内。

- nice_dev

Answer 4

/* 你需要以 R 和 C 的尊重开始循环；如果找到元素，则需要打破循环并遵循相同的过程。*/

function Diagonals(R, C, matrix, K)
{
for(let i=0; i<R;i++)
{
for(let j=0; j<C; j++)
{
if(matrix[i][j]==K)
{
r=i;
c=j;
break;

}
}
}
let sum = r+c;
let diff= r-c;
let left= "";
let right="";
for(let i=0; i<R; i++){
for(let j=0; j<C; j++){
if(i-j==diff){
left=left+matrix[i][j]+" ";
}
if(i+j==sum)
{
right=right+matrix[i][j]+" ";
}
}
}
console.log(left);
console.log(right);

}

- YOGENDRA SINGH

---

欢迎来到 [so]！请参观[导览]，访问[帮助]并阅读有关优秀回答问题的内容。 - Scott Sauyet

请对代码进行适当的缩进格式化。 - Avi Kaminetzky