如何移动数组开头的所有零项？

Question

我正在尝试解决

O(n)

中的问题，而无需

taking space

（如对象地图）。我想移动开头的所有零，一个在最后，两个在中间。

输入：[0, 1, 0, 2, 1] 预期输出：[0,0,2,1,1] 这是我的代码

let arr = [0, 1, 0, 2, 1];

function swap(input, i, j) {
    let temp = input[i];
    input[j] = input[i];
    input[i] = temp;
}

function moveZeroOneAndTwo(input) {
    let i = 0,
        j = input.length - 1;
    while (i < j) {
        while (arr[i] !== 0) i++;
        while (arr[j] !== 0) j--;

        swap(arr, j, i);
        i++;
        j--;
    }

return input
}

console.log(moveZeroOneAndTwo(arr))

我试图从左侧找到

1

索引和从

zero

找到

right

索引并交换它们仍然无法解决这个问题

Answer 1

计算 0,1,2，然后用 3 个值及其从头开始的计数填充数组..
您不需要任何额外的变量空间，只需使用原始数组即可。

let arr = [0, 1, 0, 2, 1];
let count = [0,0,0];
arr.forEach(el => count[el]++);
arr.fill(0,0,count[0]);
arr.fill(2,count[0],count[0]+count[2]);
arr.fill(1,count[0]+count[2],count[0]+count[1]+count[2]);
console.log(arr);

Answer 2

最简单的方法是从左到右扫描数组并计算 0 和 1。然后，将 0 分配给第一个 zero_count 数字，将 1 分配给最后一个 one_count 数字，将 2 分配给其他数字。

Answer 3

您可以使用荷兰国旗问题的算法

荷兰国旗问题 ¹ 是由 Edsger Dijkstra 提出的计算机科学编程问题（在他的书 编程学科 Prentice-Hall，1976 年的一章中）。 荷兰国旗由红、白、蓝三种颜色组成。给定这三种颜色的球随机排列在一条线上（球的实际数量并不重要），任务是将它们排列在一起，使所有相同颜色的球都在一起，并且它们的集体颜色组的顺序正确。

带有值的包装器。

var array = [0, 1, 0, 2, 1],
    values = [0, 2, 1],
    MID = 2,
    i = 0,
    j = 0,
    n = array.length - 1;

while (j <= n) {
    if (values[array[j]] < values[MID]) {
        [array[i], array[j]] = [array[j], array[i]];
        i++;
        j++;
    } else if (values[array[j]] > values[MID]) {
        [array[n], array[j]] = [array[j], array[n]];
        n--;
    } else {
        j++;
    }
}

console.log(array);

Answer 4

也许不如 Dijkstra 的解决方案那么优雅，但我确实自己想出了它。这个想法是保留一个指针，

r

，指向 1 部分（右侧）中最左边的非 1，并保留一个指针

l

，指向 0 部分（左侧）中最右边的 0。

现在扫描：

如果值为1，则与右侧指针处的值切换，并降低该指针；另外，如果我们现在手头有一个 0，请将其与左指针右侧的值进行交换，然后前进该指针。

否则，如果值为 0，则将其与左指针右侧的值进行切换，并使该指针前进。

（我们对每次迭代进行额外检查，如果左指针或右指针的部分增加，则分别增加或减少左指针或右指针。）

显然，它是

O(n)

，因为在每次迭代中我们要么增加

i

，要么减少

r

，或者我们有一些部分使迭代变得毫无意义。

看来最终通过了控制测试。

function f(A){
  let l = -1;
  let r = A.length - 1;
  
  for (let i=0; i<=r; i++){
    if (A[r] == 1){
      r--;
      i--;

    } else if (A[l+1] == 0){
      l++;
      i--;

    } else if (A[i] == 1){
      [A[i], A[r]] = [A[r], A[i]];
      r--;
      if (A[i] == 0){
        [A[i], A[l+1]] = [A[l+1], A[i]];
        l++;
      }
      
    } else if (A[i] == 0 && i > l + 1){
      [A[i], A[l+1]] = [A[l+1], A[i]];
      l++;
    }
  }
}

function control(arr){
  let count = [0,0,0];
  arr.forEach(el => count[el]++);
  arr.fill(0,0,count[0]);
  arr.fill(2,count[0],count[0]+count[2]);
  arr.fill(1,count[0]+count[2],count[0]+count[1]+count[2]);
}

var As = [
  [0,1,0,2,1],
  [0,1,0,1,2,2,0],
  [1,0,0,1,2,2,2],
  [0,2,1,0,1,1,1],
  [0,2,2,1,1,0,0],
  [2,0,2,2,0,1,0],
  [2,0,0,2,2,0,0],
  [1,2,0,0,0,1,1],
  [1,0,2,1,2,1,0],
  [2,1,1,1,0,0,0],
  [1,2,2,2,0,0,0],
  [1,2,1,0,0,0,2],
  [1,2,0,0,1,1,2],
  [1,0,2,1,2,0,0],
  [2,0,1,0,2,2,1]
];

for (let A of As){
  console.log('' + A);
  f(A)
  console.log('' + A);
  console.log('');
}

var numTests = 500;
var n = 10;

for (let i=0; i<numTests; i++){
  let A1 = new Array(n);
  for (let j=0; j<n; j++)
    A1[j] = ~~(Math.random() * 3);
  let A1Pre = A1.slice();
  let A2 = A1.slice();
  f(A1);
  control(A2);
  if (String(A1) != String(A2)){
    console.log('Mismatch');
    console.log(String(A1Pre));
    console.log(String(A1));
    console.log(String(A2));
    break;
  }
}

Answer 5

时间复杂度不太好，但很短：

const move0ToTheBeginning = arr => arr.sort((a, b) =>
  Math.abs(Math.sign(a)) - Math.abs(Math.sign(b))
)

Answer 6

void changeZero(int arr[], int sizesofArr)
{
    int countZero = 0, firstIndexZero = -1;
    for (int i = sizesofArr-1;i>=0; i--)
    {
        if (arr[i] == 0)
        {
            if (firstIndexZero == -1)
            {
                firstIndexZero = i;
            }
        }
        else
        {
            if (firstIndexZero != -1)
            {
                arr[firstIndexZero] = arr[i];
                arr[i] = 0;
                firstIndexZero--;
            }
        }
    }
}