合并两个有序数组、第一个错误的版本和搜索旋转排序数组

搜索文档…
合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例
1
输入:
2
nums1 = [1,2,3,0,0,0], m = 3
3
nums2 = [2,5,6],       n = 3
4
​
5
输出: [1,2,2,3,5,6]
Copied!
方法一 双指针 从前往后遍历
思路
先简化问题，从合并数组简化成合并两个元素。分别从两个数组中取出一个元素进行比较，比较完后将较小元素合并进结果数组，较大元素继续和另一个数组中取的下一个元素比较，如此循环，直到某个数组中的元素都被比较过时，剩下的数组中未被比较过的元素直接按顺序放到结果数组中。
详解
1.定义两个指针 j、k，分别指向当前 nums1 与 nums2 数组中第一个元素的下标，定义一个 result 数组存放合并结果
2.比较 nums1[j] 和 nums2[k] 两个元素，将较小元素 push 进 result 中
1.指向较小元素的指针加 1，取出上次较大元素继续比较，循环第 2 步
2.当某个数组中的元素都被比较过了，将另一数组剩余元素直接 push 到 result 中，因为两个数组都是有序数组，剩下的肯定是较大值
代码
1
/**
2
 * @param {number[]} nums1
3
 * @param {number} m
4
 * @param {number[]} nums2
5
 * @param {number} n
6
 * @return {void}
7
 */
8
const merge = function (nums1, m, nums2, n) {
9
  // 暂存 merge 结果
10
  const result = [];
11
  // 定义两个指针 j、k，分别指向当前 nums1 与 nums2 数组中正在比较值的数组下标，从前往后
12
  let j = 0; let k = 0;
13
  // 遍历 nums1 和 nums2 数组，遍历完一个数组后跳出循环
14
  while (j < m && k < n) {
15
    // 比较 nums1 中取的值与 nums2 中取的值，将较小值 push 到结果数组中
16
    // 并将下标往后加一，下次循环取后一个值进行比较
17
    if (nums1[j] > nums2[k]) {
18
      result.push(nums2[k]);
19
      k++;
20
    } else {
21
      result.push(nums1[j]);
22
      j++;
23
    }
24
  }
25
​
26
  // nums1 或 nums2 中有一个数组未遍历完全
27
  if (result.length < m + n) {
28
    // 如果 nums1 遍历完了，则说明 nums2 未遍历完全，
29
    // 将 nums2 中剩余未比较的数据直接 push 到 merge 结果数组中
30
    // 反之亦然
31
    if (j === m) {
32
      result.push(...nums2.slice(k, n));
33
    } else {
34
      result.push(...nums1.slice(j, m));
35
    }
36
  }
37
  // 清空 nums1，将 merge 结果 push 到 nums1 中
38
  nums1.splice(0, nums1.length);
39
  nums1.push(...result);
40
};
Copied!
复杂度分析
时间复杂度： O(m+n)O(m + n)O(m+n)
​
最多遍历 m+n−1m + n -1m+n−1
 次，所以时间复杂度为 O(m+n)O(m + n)O(m+n)
​
空间复杂度：O(m)O(m)O(m)
​
开辟新的空间存放 nums1 数组，所以空间复杂度为 O(m)O(m)O(m)
​
方法二 双指针 从后往前遍历
思路
先简化问题，从合并数组简化成合并两个元素。因为 nums1 数组长度可以存放最后排序好的元素，所以可以从后往前取两个数组的元素进行比较，从 nums1 数组的最后开始存放较大元素。较小值继续与新取出的元素进行比较，如此循环直到某个数组中的元素全部被比较过，可得最终结果。
详解
1.定义一个指针 p，指向 nums1 数组最后一个位置(m + n - 1)。 2.比较 nums1[m - 1] 和 nums2[n - 1] 两个元素，将较大元素放到 nums1[p] 中 3.指针 p 往前移动一位，，较大元素所在数组往前继续取出一个元素与上次较小元素进行比较，将较大元素放到 nums1[p] 中 4.循环第 3 步，直到某个数组中的元素全部被比较过，因为 nums1 和 nums2 数组都是有序数组，所以另一数组未比较的元素肯定是较小的那部分元素，直接将剩余元素放到 nums1 的头部
代码
1
/**
2
 * @param {number[]} nums1
3
 * @param {number} m
4
 * @param {number[]} nums2
5
 * @param {number} n
6
 * @return {void}
7
 */
8
const merge = function (nums1, m, nums2, n) {
9
  let currentInsertIndex = nums1.length - 1;
10
  while (currentInsertIndex >= 0 && n > 0 && m > 0) {
11
    if (nums1[m - 1] > nums2[n - 1]) {
12
      nums1[currentInsertIndex--] = nums1[m - 1];
13
      m--;
14
    } else {
15
      nums1[currentInsertIndex--] = nums2[n - 1];
16
      n--;
17
    }
18
  }
19
​
20
  // nums2 未遍历完成，将 nums2 中剩余未遍历的数据插入到 nums1 头部
21
  // nums1 未遍历完成不用关心，已排序好了
22
  if (n > 0) {
23
    nums1.splice(0, n, ...nums2.slice(0, n));
24
  }
25
};
Copied!
复杂度分析
时间复杂度：O(m+n)O(m + n)O(m+n)
​
最多遍历 m+n−1m + n - 1m+n−1
 次，所以时间复杂度为 O(m+n)O(m + n)O(m+n)
​
空间复杂度： O(1)O(1)O(1)
​
不需要开辟新的空间，所以空间复杂度为 O(1)O(1)O(1)
​
方法三 利用 array.sort()方法
思路
直接合并两个数组并排序
详解
1.将 nums1 后面的占位删除并将 nums2 合并 2.用 array.sort() 方法排序
代码
1
/**
2
 * @param {number[]} nums1
3
 * @param {number} m
4
 * @param {number[]} nums2
5
 * @param {number} n
6
 * @return {void}
7
 */
8
const merge = function (nums1, m, nums2, n) {
9
  // 两数组合并，将 nums1 后面的占位删除并放入 nums2
10
  nums1.splice(m, n, ...nums2);
11
  // 排序
12
  nums1.sort((a, b) => a - b);
13
};
Copied!
复杂度分析
时间复杂度：O(nlogn)O(nlogn)O(nlogn)
​
排序在 v8 引擎下的平均时间复杂度为 O(nlogn)O(nlogn)O(nlogn)
​
空间复杂度：O(nlogn)O(nlogn)O(nlogn)
​
排序在 v8 引擎下的平均空间复杂度为 O(nlogn)O(nlogn)O(nlogn)
​
第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 示例 
1
给定 n = 5，并且 version = 4 是第一个错误的版本。
2
​
3
调用 isBadVersion(3) -> false
4
调用 isBadVersion(5) -> true
5
调用 isBadVersion(4) -> true
6
​
7
所以，4 是第一个错误的版本。
Copied!
方法一 暴力法[超出时间限制]
思路
直接for循环找第一个错误版本。
代码
1
const solution = function(isBadVersion) {
2
  return function firstBadVersion (n) {
3
    for (let i = 1; i < n; i++) {
4
      if (isBadVersion(i)) {
5
        return i;
6
      }
7
    }
8
    return n;
9
  }
10
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
该方法需要遍历每一个元素，需要耗费O(n)O(n)O(n)
时间，当遇见版本特别多的时候O(n)的时间，因此改方法时间复杂度为O(n)O(n)O(n)
。
空间复杂度：O(1)O(1)O(1)
​
该方法没有申请额外的空间，所以空间复杂度为O(1)O(1)O(1)
​
方法二 二分法
思路
前一种方法需要遍历每一个元素，这样如果元素特别多的时候会耗时过多，这个时候通过二分法也就是折半法(有序数组中查找特定元素的搜索算法)来查找元素。
二分法思路：
1.首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
2.如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。
3.如果某一步数组为空，则表示找不到目标元素。
这样可以避免无差别遍历降低遍历耗时。
详解
1.确定数组左边边界值和右边边界值，找到边界值的中间值
2.比较中间值是否是错误版本，如果是则右边边界值=中间值-1，再找中间值比较。如果不是错误版本则左侧边界值=中间值+1，再找左侧值和右侧值之间的中间值比较，这样重复下去
3.当左侧边界值>右侧边界值得时候，说明右侧已经全是错误版本了，当前左侧的值就是临界值
代码
1
const solution = function(isBadVersion) {
2
  return function firstBadVersion (n) {
3
    let left = 1;
4
    let right = n;
5
    while (left <= right) {
6
      const mid = Math.floor(left + (right - left) / 2);
7
      if (isBadVersion(mid)) {
8
        right = mid - 1;
9
      } else {
10
        left = mid + 1;
11
      }
12
    }
13
    return left;
14
  }
15
}
Copied!
复杂度分析
时间复杂度为: O(log⁡2(n))O(\log_2(n))O(log2​(n))
​
对于n个元素的情况(去掉常数)
第一次二分：n/2n/2n/2
​
第二次二分：n/22=n/4n/2^2= n/4n/22=n/4
、......
m次二分：n/(2m)n/(2^m)n/(2m)
​
在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为n/(2m)n/(2^m)n/(2m)
=1，得到 2m=n2^m=n2m=n
​
所以时间复杂度为：O(log⁡2(n))O(\log_2(n))O(log2​(n))
​
空间复杂度：O(1)O(1)O(1)
 该方法没有申请额外的空间，所以空间复杂度为O(1)O(1)O(1)
​
搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
1
输入: nums = [4,5,6,7,0,1,2], target = 0
2
输出: 4
Copied!
示例 2:
1
输入: nums = [4,5,6,7,0,1,2], target = 3
2
输出: -1
Copied!
方法一 二分查询最大最小值
思路
先算出 数组中最大最小值，利用 indexOf 计算之后要旋转位置，然后二分计算目标 target 位置
详解
1.计算数组中的最大最小值
2.定义变量，数组长度等
3.目标值大于数组最后一位时，数组查询位置从 0 到数字中在最大位置
4.目标值小于等于数组最后一位时，数组查询位置从数组中最小值的位置开始，到数组的最后一位，3.4 两部为了定位数组查询区间
5.循环二分查询，计算定位数组的中间值，数组的值等于目标查询结束
6.不等于的情况，如果目标大于中间值，则定位数组最小值等于中间值+1，目标小于中间值，则定位数组中最大值等于中间值-1，继续循环查询即可，知道定位数组查询完毕，没有结果的话，返回 -1 代表不存在
代码
1
const search = function (nums, target) {
2
  const min = Math.min.apply(null, nums);
3
  const max = Math.max.apply(null, nums);
4
  const len = nums.length;
5
  let pos;
6
  let lo;
7
  let hi;
8
  let mid;
9
​
10
  if (target > nums[len - 1]) {
11
    pos = nums.indexOf(max);
12
    lo = 0;
13
    hi = pos;
14
  } else {
15
    pos = nums.indexOf(min);
16
    lo = pos;
17
    hi = len - 1;
18
  }
19
  while (lo <= hi) {
20
    mid = Math.ceil((lo + hi) / 2);
21
    if (nums[mid] === target) return mid;
22
    if (nums[mid] < target) {
23
      lo = mid + 1;
24
    } else {
25
      hi = mid - 1;
26
    }
27
  }
28
  return -1;
29
};
Copied!
复杂度分析：
时间复杂度：O(log(n))O(log(n))O(log(n))
​
过程会最多遍历一遍数组
空间复杂度：O(1)O(1)O(1)
​
只产生一次临时变量存储
方法二 二分查询中间数
思路
根据数组的中间数和左右节点的大小对比，来确定升序部分的位置，然后用二分法查询目标节点在数组中的位置
详解
1.计算数组长度，数组为0 直接返回-1
2.定义左右值分别为数组第一个和最后一个的下标
3.中间下标值为最大最小值的平均数
4.如果数组中间数等于目标直接返回下标
5.数组的中间值小于数组最后一个值，后半部分还处于升序，如果目标值在这部分数组中，则左下标等于中间值+1，代表目标值在后半部分数组，反着重新定义右下标为中间值-1，目标在前半数组
6.数组中间值大于数组最后一个值，代表前半部分数组处于升序，如果目标在前半数组中，右标更新为中间值-1，反之，左下标更新为中间值+1
7.二分查询到最后没找到目标值，则返回 -1 代表不存在
代码
1
const search = function(nums, target) {
2
  if(nums.length === 0){
3
    return -1;
4
  }
5
​
6
  let left = 0;
7
  let right = nums.length - 1;
8
  let mid;
9
​
10
  while(left <= right){
11
    mid = parseInt((left + right) / 2);
12
    if(nums[mid] === target){
13
      return mid;
14
    } else if(nums[mid] < nums[right]) {
15
      if(nums[mid] < target && target <= nums[right]) {
16
            left = mid + 1;
17
      } else {
18
        right = mid - 1;
19
      }
20
    } else {
21
      if(nums[left] <= target && target < nums[mid]){
22
            right = mid - 1;
23
      } else {
24
        left = mid + 1;
25
      }
26
    }
27
  }
28
  return -1;
29
};
Copied!
复杂度分析
时间复杂度：O(log(n))O(log(n))O(log(n))
​
过程会最多遍历一遍数组
空间复杂度：O(1)O(1)O(1)
​
只产生一次临时变量存储