TS数据结构与算法之移动0到数组的末尾

问题

• 将数组中的0移动到末尾
• 如输入 [1, 0, 3, 0, 11, 0], 输出 [1, 3, 11, 0, 0, 0]
• 只移动0， 其它顺序不变
• 必须在原数组进行操作

方案1：如果不限制“必须在原数组操作”

• 定义 part1, part2 两个数组
• 遍历数组，非0 push到 part1， 0 push 到 part2
• 最后返回 part1.concat(part2)

此方案非常简单，但不符合第3限制条件

方案2：传统思路

• 遍历数组，遇到 0 则 push 到数组末尾
• 用 splice 截取掉当前元素
• 此方案时间复杂度是 O(n^2) —— 算法不可用

代码演示

/**
 * 移动 0 到数组和末尾（嵌套循环）
 */
export const moveZero1 = (arr: number[]): void => {
  const len = arr.length;
  if (!len) return;

  let zeroLength = 0;
  // 整体 O(n^2)
  for (let i = 0; i < len - zeroLength; i++) {
    if (arr[i] === 0) {
      arr.push(0);
      // 本身就有 O(n)
      arr.splice(i, 1);
      // [1, 0, 0, 0, 1, 0]
      // 数组截取了一个元素， i 要递减，否则连续 0 就会有错误
      i --;
      zeroLength ++; // 累加 0 的长度
    }
  }
}

方案3 - 优化使用双指针

• 定义 j 指向第一个 0，i 指向 j 后面的第一个非 0
• 交换 i 和 j 的值，继续向后移动
• 只遍历一次，所以时间复杂度是 O(n)

[1, 0, 0, 1, 1, 0]
    j     i

交换：

[1, 1, 0, 0, 1, 0]
       j     i

再交换

[1, 1, 1, 0, 0, 0]

代码演示

/**
 * 移动 0 到数组和末尾（双指针）
 */
export const moveZero2 = (arr: number[]): void => {
  const len = arr.length;
  if (!len) return;

  let i;
  let j = -1; // 指向第一个0

  for (i = 0; i < len; i++) {
    if (arr[i] === 0) {
      // 第一个0
      if (j < 0) {
        j = i;
      }
    }

    // i 指向第一个非0 j指向第一个0时
    if (arr[i] !== 0 && j >= 0) {
      // 交换
      const n = arr[i];
      arr[i] = arr[j];
      arr[j] = n;

      // j 向后移动
      j++;
    }
  }
};

功能测试

export const moveZeroFunctionalTest = () => {
  const arr = [1, 0, 3, 4, 0, 0, 11, 0];
  moveZero2(arr);
  console.log(arr); // [1, 3, 4, 11, 0, 0, 0, 0]
};

单元测试

/**
 * @description 将0移动到数组末尾单元测试
 */
import { moveZero2 } from '../src/utils/move-zero';
describe('移动0到数组末尾', () => {
  test('正常情况', () => {
    const arr = [1, 0, 3, 4, 0, 0, 0, 11, 0];
    moveZero2(arr);
    expect(arr).toEqual([1, 3, 4, 11, 0, 0, 0, 0, 0]);
  });

  test('没有0', () => {
    const arr = [1, 3, 4, 11];
    moveZero2(arr);
    expect(arr).toEqual([1, 3, 4, 11]);
  });

  test('全是0', () => {
    const arr = [0, 0, 0, 0, 0];
    moveZero2(arr);
    expect(arr).toEqual([0, 0, 0, 0, 0]);
  });
});

运行 yarn jest:

PASS  tests/move-zero.test.ts
  移动0到数组末尾
    √ 正常情况 (1 ms)
    √ 没有0
    √ 全是0

性能测试

分别使用两种方案操作有20W条数据的数组

// 性能测试
export const moveZeroPerformanceTest = () => {
  const arr1 = [];
  for (let i = 0; i < 20 * 10000; i++) {
    if (i % 10 === 0) {
      arr1.push(0);
    } else {
      arr1.push(i);
    }
  }
  console.time('moveZero1');
  moveZero1(arr1);
  console.timeEnd('moveZero1');

  const arr2 = [];
  for (let i = 0; i < 20 * 10000; i++) {
    if (i % 10 === 0) {
      arr2.push(0);
    } else {
      arr2.push(i);
    }
  }
  console.time('moveZero2'); 
  moveZero2(arr2);
  console.timeEnd('moveZero2');
}

输出：

• moveZero1: 2006.822998046875 ms
• moveZero2: 1.85302734375 ms

重点

• 首先先确认： 是否必须修改原数组？
• 数组是连续存储，要慎用 splice unshift 等 API
• 双指针思路