算法复习-数组

数组

JavaScript 中， Array 继承自 Object ，或者说它就是一个特殊的对象，内部是以 key-value 形式存储数据，所以 JavaScript 中的数组可以存放不同类型的值。它有两种存储方式，快数组与慢数组，初始化空数组时，使用快数组，快数组使用连续的内存空间，当数组长度达到最大时， Array 会进行动态的扩容，以存储更多的元素，相对慢数组，性能要好得多。当数组中 hole 太多时，会转变成慢数组，即以哈希表的方式（ key-value 的形式）存储数据，以节省内存空间。

合并两数组

const first = (arr) => arr[0];
const last = (arr) => arr[arr.length - 1];

function combineOrderedArrays(arr1, arr2) {
  if (!Array.isArray(arr1) || !Array.isArray(arr2)) throw new TypeError('parameter must be an array');
  if (arr1.length === 0) return arr2;
  if (arr2.length === 0) return arr1;
  if (first(arr1) >= last(arr2)) return arr1.concat(arr2);
  if (first(arr2) >= last(arr1)) return arr2.concat(arr1);

  let index1 = arr1.length - 1;
  let index2 = arr2.length - 1;
  let index = arr1.length + arr2.length - 1;
  const res = [...arr1];
  while (index2 >= 0) {
    if (index1 < 0) {
      res[index] = arr2[index2];
      index -= 1;
      index2 -= 1;
    } else {
      if (arr2[index2] > arr1[index1]) {
        res[index] = arr2[index2];
        index2 -= 1;
      } else {
        res[index] = arr1[index1];
        index1 -= 1;
      }
      index -= 1;
    }
  }

  return res;
}

数组两数之和

function sumOfTwoNumbers(src, target) {
  if (!Array.isArray(src)) throw new TypeError('src must be an Array');
  const tmp = new Map();
  for (let i = 0; i < src.length; i += 1) {
    const abs = target - src[i];
    if (tmp.has(abs)) return [tmp.get(abs), i];
    tmp.set(src[i], i);
  }
  return [];
}

数组交集

function intersection(arr1, arr2) {
  if (!Array.isArray(arr1) || !Array.isArray(arr2)) throw new TypeError('parameters must be both of Arrays');
  const tmp = new Set(arr1);
  const res = new Set();
  arr2.forEach((item) => {
    if (tmp.has(item)) res.add(item);
  });

  return Array.from(res);
}

参考

前端进阶算法2：从Chrome V8源码看JavaScript数组（附赠腾讯面试题）