数组算法题

1. 数组中第二大的数字【经典】

思路：设置两个变量 a，b；数组在 arr[]中，假设 arr[0]最大，记为 a；arr[1]第二大，记为 b；若 a 小于 b，则交换值。遍历数组，若元素大于 a，则 a 的值赋给 b，最大值赋给 a；若元素小于 a，大于 b，则元素赋值给 b，遍历完毕，b 为次大值，

时间复杂度: O（n）

var arr = [2, 4, 14, 20, 8, 3, 15];
var a = arr[0],
  b = arr[1];
if (a < b) {
  var temp = a;
  a = b;
  b = temp;
}
for (var i = 2; i < arr.length; i++) {
  if (arr[i] > a) {
    b = a;
    a = arr[i];
  } else if (arr[i] < a && arr[i] > b) {
    b = arr[i];
  }
}

2. 合并两个有序数组【L88】

1. 逆向双指针

时间复杂度：O(m+n)。指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。

空间复杂度：O(1)。直接对数组 nums1 原地修改，不需要额外空间。

var merge = function(nums1, m, nums2, n) {
  let p1 = m - 1,
    p2 = n - 1;
  let tail = m + n - 1;
  var cur;
  while (p1 >= 0 || p2 >= 0) {
    if (p1 === -1) {
      cur = nums2[p2--];
    } else if (p2 === -1) {
      cur = nums1[p1--];
    } else if (nums1[p1] > nums2[p2]) {
      cur = nums1[p1--];
    } else {
      cur = nums2[p2--];
    }
    nums1[tail--] = cur;
  }
};

2. 双指针

时间复杂度：O(m+n)。指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。

空间复杂度：O(m+n)。需要建立长度为 m+n 的中间数组 sorted。

var merge = function(nums1, m, nums2, n) {
  let p1 = 0,
    p2 = 0;
  const sorted = new Array(m + n).fill(0);
  var cur;
  while (p1 < m || p2 < n) {
    if (p1 === m) {
      cur = nums2[p2++];
    } else if (p2 === n) {
      cur = nums1[p1++];
    } else if (nums1[p1] < nums2[p2]) {
      cur = nums1[p1++];
    } else {
      cur = nums2[p2++];
    }
    sorted[p1 + p2 - 1] = cur;
  }
  for (let i = 0; i != m + n; ++i) {
    nums1[i] = sorted[i];
  }
};

3. 直接合并后排序

时间复杂度：O((m+n)log(m+n))。排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n))。

空间复杂度：O(log(m+n))。排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。

var merge = function(nums1, m, nums2, n) {
  nums1.splice(m, nums1.length - m, ...nums2);
  nums1.sort((a, b) => a - b);
};

3. 两数之和【L1】

题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

1. 哈希表 map

解题过程：运用逆向解法，即用 target 减去数组中的某个元素，然后来判断 map 中是否有相同的值，若有则存在满足条件的答案，返回两个坐标即可；若没有，则保存{数组中某个元素值，对应的坐标}到 map 对象中。依次遍历即可判断是否有满足条件的两个元素。

var twoSum = function(nums, target) {
  let map = new Map();
  for (let i = 0, len = nums.length; i < len; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i];
    } else {
      map.set(nums[i], i);
    }
  }
  return [];
};

4. 三数之和为 0【L15】

题目描述：给你一个包含 n 个整数的数组  nums，判断  nums  中是否存在三个元素 a，b，c ，使得  a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

1. 排序 + 双指针

（1）首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集

（2）如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环

（3）如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过

（4）当 sum == 00 时，nums[L]== nums[L+1] 则会导致结果重复，应该跳过，L++

（5）当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R--

时间复杂度：O(n^2)，n 为数组长度

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  if (nums.length < 3) {
    return [];
  }
  const result = [];
  nums.sort((a, b) => a - b);

  let leftIdx, rightIdx;
  // 固定首个元素
  for (let i = 0; i < nums.length; i++) {
    // 固定元素大于0跳过，重复固定下一个
    if (nums[i] > 0) break;
    if (nums[i] === nums[i - 1]) continue;

    // 双指针指向
    (leftIdx = i + 1), (rightIdx = nums.length - 1);
    while (leftIdx < rightIdx) {
      // 大于右指针左移 小于左指针右移
      if (nums[leftIdx] + nums[rightIdx] + nums[i] > 0) {
        rightIdx--;
      } else if (nums[leftIdx] + nums[rightIdx] + nums[i] < 0) {
        leftIdx++;
      } else {
        result.push([nums[i], nums[leftIdx], nums[rightIdx]]);
        while (
          leftIdx < rightIdx &&
          nums[leftIdx] === nums[leftIdx + 1] //跳过重复元素
        )
          leftIdx++;
        while (
          leftIdx < rightIdx &&
          nums[rightIdx] === nums[rightIdx - 1] //同上
        )
          rightIdx--;
        // 符合要求元素用过 指针移动
        leftIdx++;
        rightIdx--;
      }
    }
  }

  return result;
};

5. 四数之和 【L18】

1. 排序 + 双指针

时间复杂度：O(n^3)其中 n 是数组的长度。排序的时间复杂度是 O(nlogn)，枚举四元组的时间复杂度是 O(n^3)，因此总时间复杂度为 O(n^3+nlogn)=O(n^3)

空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组 nums，实际情况中不一定允许，因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序，空间复杂度为 O(n)。

var fourSum = function(nums, target) {
  if (nums.length < 4) {
    return [];
  }
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
      break;
    }
    for (let j = i + 1; j < nums.length - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) {
        continue;
      }
      let left = j + 1,
        right = nums.length - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          result.push([nums[i], nums[j], nums[left], nums[right]]);
        }
        if (sum <= target) {
          while (nums[left] === nums[++left]);
        } else {
          while (nums[right] === nums[--right]);
        }
      }
    }
  }
  return result;
};

6. 最大子数组和【L53 O42】

• 1. 动态规划

这有点类似「滚动数组」的思想

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。

var maxSubArray = function(nums) {
  let res = nums[0];
  for (let i = 1; i < nums.length; ++i) {
    // 如果前一个的累加和小于0，就不要累加了
    if (nums[i - 1] > 0) {
      nums[i] += nums[i - 1];
    }
    res = Math.max(res, nums[i]);
  }
  return res;
};

var maxSubArray = function(nums) {
  let pre = 0,
    maxAns = nums[0];
  nums.forEach((x) => {
    pre = Math.max(pre + x, x);
    maxAns = Math.max(maxAns, pre);
  });
  return maxAns;
};

2. 分治

7. 把数组排成最小的数【O45】

/**
 * @param {number[]} nums
 * @return {string}
 */
var minNumber = function(nums) {
  function compare(a, b) {
    var sumA = "" + a + b;
    var sumB = "" + b + a;
    return sumA - sumB;
  }
  return nums.sort(compare).join("");
};

8. 数组中的第 k 大的数字【L215，O76】

1. 快速排序的 partition 分区

实现过程：

（1）在长度为 n 的排序数组中，第 k 大的数字的下标是 n-k

（2）用快速排序的函数 partition 对数组分区，如果函数 partition 选取的中间值在分区之后的下标正好是 n-k，分区后左边的的值都比中间值小，右边的值都比中间值大，即使整个数组不是排序的，中间值也肯定是第 k 大的数字

（3）如果函数 partition 选取的中间值在分区之后的下标大于 n-k，那么第 k 大的数字一定位于中间值的左侧，于是再对中间值的左侧的子数组分区

（4）如果函数 partition 选择的中间值在分区之后的下标小于 n-k，那么第 k 大的数字一定位于中间值的右侧，于是再对中间值的右侧的子数组分区

// 单边循环法
function partition(arr, startIndex, endIndex) {
  // 取第一个位置的元素作为基准元素（也可以选择随机位置）
  let pivot = arr[startIndex];
  // 设置一个 mark 指针指向数组起始位置 -- 最终 这个 mark 指针代表小于基准元素的区域边界
  let mark = startIndex;
  for (let i = startIndex + 1; i <= endIndex; i++) {
    if (arr[i] < pivot) {
      mark++;
      [arr[mark], arr[i]] = [arr[i], arr[mark]];
    }
  }
  arr[startIndex] = arr[mark];
  arr[mark] = pivot;
  return mark;
}
var findKthLargest = function(nums, k) {
  let targetIndex = nums.length - k;
  let start = 0,
    end = nums.length - 1;
  let index = partition(nums, start, end);
  while (index != targetIndex) {
    if (index > targetIndex) {
      end = index - 1;
    } else {
      start = index + 1;
    }
    index = partition(nums, start, end);
  }
  return nums[index];
};

2. 小顶堆法：构造前 k 个最大元素小顶堆，取堆顶

时间复杂度 O(nlogk)，循环 n 次，每次堆的操作是 O(logk)。

空间复杂度 O(k)，

排序说明：

（1）升序：一般采用大顶堆

（2）降序：一般采用小顶堆

原理：维护大小为 k 的小顶堆，当堆的元素个数小于等于 k 时，遍历数组，让数组的元素不断加入堆，当堆的大小大于 k 时，让堆顶元素出列，遍历完数组之后，小顶堆堆顶的元素就是第 k 大元素。

class Heap {
  constructor(comparator = (a, b) => a - b, data = []) {
    this.data = data;
    this.comparator = comparator; //比较器
    this.heapify(); //堆化
  }

  heapify() {
    if (this.size() < 2) return;
    for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {
      this.bubbleDown(i); //bubbleDown操作
    }
  }

  peek() {
    if (this.size() === 0) return null;
    return this.data[0]; //查看堆顶
  }

  offer(value) {
    this.data.push(value); //加入数组
    this.bubbleUp(this.size() - 1); //调整加入的元素在小顶堆中的位置
  }

  poll() {
    if (this.size() === 0) {
      return null;
    }
    const result = this.data[0];
    const last = this.data.pop();
    if (this.size() !== 0) {
      this.data[0] = last; //交换第一个元素和最后一个元素
      this.bubbleDown(0); //bubbleDown操作
    }
    return result;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = (index - 1) >> 1; //父节点的位置
      //如果当前元素比父节点的元素小，就交换当前节点和父节点的位置
      if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
        this.swap(index, parentIndex); //交换自己和父节点的位置
        index = parentIndex; //不断向上取父节点进行比较
      } else {
        break; //如果当前元素比父节点的元素大，不需要处理
      }
    }
  }

  bubbleDown(index) {
    const lastIndex = this.size() - 1; //最后一个节点的位置
    while (true) {
      const leftIndex = index * 2 + 1; //左节点的位置
      const rightIndex = index * 2 + 2; //右节点的位置
      let findIndex = index; //bubbleDown节点的位置
      //找出左右节点中value小的节点
      if (
        leftIndex <= lastIndex &&
        this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
      ) {
        findIndex = leftIndex;
      }
      if (
        rightIndex <= lastIndex &&
        this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
      ) {
        findIndex = rightIndex;
      }
      if (index !== findIndex) {
        this.swap(index, findIndex); //交换当前元素和左右节点中value小的
        index = findIndex;
      } else {
        break;
      }
    }
  }

  swap(index1, index2) {
    //交换堆中两个元素的位置
    [this.data[index1], this.data[index2]] = [
      this.data[index2],
      this.data[index1],
    ];
  }

  size() {
    return this.data.length;
  }
}

var findKthLargest = function(nums, k) {
  const h = new Heap((a, b) => a - b);

  for (const num of nums) {
    h.offer(num); //加入堆
    if (h.size() > k) {
      //堆的size超过k时，出堆
      h.poll();
    }
  }

  return h.peek();
};

3. 先 sort 排序，后取值

var findKthLargest = function(nums, k) {
  nums = nums.sort((a, b) => a - b);
  return nums[nums.length - k];
};

9. 找出数组中第 k 大的数字出现多少次。

10. 数组中数字出现的次数【O56】

题目描述：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。

题解：直接用 Map 统计各个数出现的次数。在遍历一次 Map，返回出现次数为 1 的数。

const singleNumber = (nums) => {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    map.set(nums[i], (map.get(nums[i]) || 0) + 1);
  }
  for (const item of map) {
    if (item[1] === 1) return item[0];
  }
};

延伸：统计数字在数组中出现的次数

const singleNumber = (nums, num) => {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    map.set(nums[i], (map.get(nums[i]) || 0) + 1);
  }
  return map.get(num);
};

11.寻找两个正序数组的中位数【L4】

1. 二分查找法

var findMedianSortedArrays = function(nums1, nums2) {
  // 保证num1是比较短的数组
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }
  const length1 = nums1.length;
  const length2 = nums2.length;
  let min = 0;
  let max = length1;
  let half = Math.floor((length1 + length2 + 1) / 2);
  while (max >= min) {
    const i = Math.floor((max + min) / 2);
    const j = half - i;
    if (i > min && nums1[i - 1] > nums2[j]) {
      max = i - 1;
    } else if (i < max && nums1[i] < nums2[j - 1]) {
      min = i + 1;
    } else {
      let left, right;
      if (i === 0) left = nums2[j - 1];
      else if (j === 0) left = nums1[i - 1];
      else left = Math.max(nums1[i - 1], nums2[j - 1]);

      if (i === length1) right = nums2[j];
      else if (j === length2) right = nums1[i];
      else right = Math.min(nums1[i], nums2[j]);

      return (length1 + length2) % 2 ? left : (left + right) / 2;
    }
  }
  return 0;
};

100. 判断数组中是否有重复数

1. 先 sort 排序，然后判断索引，前一个值是否等于后一个

2. 转为 set，判断 set 大小和数组长度是否一致

数组基础算法题

1. 数组去重

基本数据类型数组去重

function unique(arr) {
  return [...new Set(arr)];
}

对象数组去重(利用对象的键名不能重复的特点)

function unique(arr) {
  let unique = {};
  arr.forEach(function(item) {
    unique[JSON.stringify(item)] = item; //键名不会重复
  });
  arr = Object.keys(unique).map(function(u) {
    //Object.keys()返回对象的所有键值组成的数组，map方法是一个遍历方法，返回遍历结果组成的数组.将unique对象的键名还原成对象数组
    return JSON.parse(u);
  });
  return arr;
}

2. 数组扁平化

层数为 1 层的扁平化：

1. arr.flat([depth]), depth 是指定的深度，默认为 1

层数为 n 层的扁平化：

1. 递归

function arrFlat(arr) {
  for (item of arr) {
    if (Array.isArray(item)) {
      return fn([].concat(...arr));
    }
  }
  return arr;
}

2. toString

function arrFlat(arr) {
  let newArr = arr.toString().split(",");
  let arrnum = newArr.map((val) => {
    return parseInt(val);
  });
  return arrnum;
}

3. 数组并集，交集，差集

• 并集

// ES7（语法） includes
function unionES7(aArr, bArr) {
  return aArr.concat(bArr.filter((v) => !aArr.includes(v)));
}
// ES6（语法） Array.from
function unionES6(aArr, bArr) {
  return Array.from(new Set(aArr.concat(bArr)));
}
// ES5（语法） indexOf
function unionES5(aArr, bArr) {
  return aArr.concat(
    bArr.filter(function(v) {
      return aArr.indexOf(v) === -1;
    })
  );
}

• 交集

// ES7（语法） includes
function interES7(aArr, bArr) {
  return aArr.filter((v) => bArr.includes(v));
}
// ES6（语法） Array.from
function interES6(aArr, bArr) {
  // let aSet = new Set(aArr)
  let bSet = new Set(bArr);
  return Array.from(new Set(aArr.filter((v) => bSet.has(v))));
}
// ES5（语法） indexOf
function interES5(aArr, bArr) {
  return aArr.filter(function(v) {
    return bArr.indexOf(v) > -1;
  });
}

• a-b 差集

// ES7（语法） includes
function diffES7(aArr, bArr) {
  //  filter() 不会改变原始数组
  return aArr.concat(bArr).filter((v) => aArr.includes(v) && !bArr.includes(v));
}
// ES6（语法） Array.from
function diffES6(aArr, bArr) {
  let aSet = new Set(aArr);
  let bSet = new Set(bArr);
  return Array.from(
    new Set(aArr.concat(bArr).filter((v) => aSet.has(v) && !bSet.has(v)))
  );
}
// ES5（语法） indexOf
function diffES5(aArr, bArr) {
  return aArr.filter(function(v) {
    return bArr.indexOf(v) === -1;
  });
}

• a-b 差集和 b-a 差集的合集（a,b 数组不同元素的合集）

// ES7（语法） includes
function diffMergeES7(aArr, bArr) {
  //  filter() 不会改变原始数组
  return aArr
    .filter((v) => !bArr.includes(v))
    .concat(bArr.filter((v) => !aArr.includes(v)));
}
// ES6（语法） Array.from
function diffMergeES6(aArr, bArr) {
  let aSet = new Set(aArr);
  let bSet = new Set(bArr);
  return Array.from(
    new Set(
      aArr.filter((v) => !bSet.has(v)).concat(bArr.filter((v) => !aSet.has(v)))
    )
  );
}
// ES5（语法） indexOf
function diffMergeES5(aArr, bArr) {
  //  filter() 不会改变原始数组
  return aArr
    .filter((v) => bArr.indexOf(v) === -1)
    .concat(bArr.filter((v) => aArr.indexOf(v) === -1));
}

二维数组算法题