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

合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

方法一 双指针 从前往后遍历

思路

先简化问题,从合并数组简化成合并两个元素。分别从两个数组中取出一个元素进行比较,比较完后将较小元素合并进结果数组,较大元素继续和另一个数组中取的下一个元素比较,如此循环,直到某个数组中的元素都被比较过时,剩下的数组中未被比较过的元素直接按顺序放到结果数组中。

详解

  1. 定义两个指针 j、k,分别指向当前 nums1 与 nums2 数组中第一个元素的下标,定义一个 result 数组存放合并结果

  2. 比较 nums1[j] 和 nums2[k] 两个元素,将较小元素 push 进 result 中

    1. 指向较小元素的指针加 1,取出上次较大元素继续比较,循环第 2 步

    2. 当某个数组中的元素都被比较过了,将另一数组剩余元素直接 push 到 result 中,因为两个数组都是有序数组,剩下的肯定是较大值

代码

/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void}
*/
const merge = function (nums1, m, nums2, n) {
// 暂存 merge 结果
const result = [];
// 定义两个指针 j、k,分别指向当前 nums1 与 nums2 数组中正在比较值的数组下标,从前往后
let j = 0; let k = 0;
// 遍历 nums1 和 nums2 数组,遍历完一个数组后跳出循环
while (j < m && k < n) {
// 比较 nums1 中取的值与 nums2 中取的值,将较小值 push 到结果数组中
// 并将下标往后加一,下次循环取后一个值进行比较
if (nums1[j] > nums2[k]) {
result.push(nums2[k]);
k++;
} else {
result.push(nums1[j]);
j++;
}
}
// nums1 或 nums2 中有一个数组未遍历完全
if (result.length < m + n) {
// 如果 nums1 遍历完了,则说明 nums2 未遍历完全,
// 将 nums2 中剩余未比较的数据直接 push 到 merge 结果数组中
// 反之亦然
if (j === m) {
result.push(...nums2.slice(k, n));
} else {
result.push(...nums1.slice(j, m));
}
}
// 清空 nums1,将 merge 结果 push 到 nums1 中
nums1.splice(0, nums1.length);
nums1.push(...result);
};

复杂度分析

  • 时间复杂度: O(m+n)O(m + n)

    最多遍历 m+n1m + n -1 次,所以时间复杂度为 O(m+n)O(m + n)

  • 空间复杂度:O(m)O(m)

    开辟新的空间存放 nums1 数组,所以空间复杂度为 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 的头部

代码

/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void}
*/
const merge = function (nums1, m, nums2, n) {
let currentInsertIndex = nums1.length - 1;
while (currentInsertIndex >= 0 && n > 0 && m > 0) {
if (nums1[m - 1] > nums2[n - 1]) {
nums1[currentInsertIndex--] = nums1[m - 1];
m--;
} else {
nums1[currentInsertIndex--] = nums2[n - 1];
n--;
}
}
// nums2 未遍历完成,将 nums2 中剩余未遍历的数据插入到 nums1 头部
// nums1 未遍历完成不用关心,已排序好了
if (n > 0) {
nums1.splice(0, n, ...nums2.slice(0, n));
}
};

复杂度分析

  • 时间复杂度:O(m+n)O(m + n)

    最多遍历 m+n1m + n - 1 次,所以时间复杂度为 O(m+n)O(m + n)

  • 空间复杂度: O(1)O(1)

    不需要开辟新的空间,所以空间复杂度为 O(1)O(1)

方法三 利用 array.sort()方法

思路

直接合并两个数组并排序

详解

1.将 nums1 后面的占位删除并将 nums2 合并 2.用 array.sort() 方法排序

代码

/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void}
*/
const merge = function (nums1, m, nums2, n) {
// 两数组合并,将 nums1 后面的占位删除并放入 nums2
nums1.splice(m, n, ...nums2);
// 排序
nums1.sort((a, b) => a - b);
};

复杂度分析

  • 时间复杂度:O(nlogn)O(nlogn)

    排序在 v8 引擎下的平均时间复杂度为 O(nlogn)O(nlogn)

  • 空间复杂度:O(nlogn)O(nlogn)

    排序在 v8 引擎下的平均空间复杂度为 O(nlogn)O(nlogn)

第一个错误的版本

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例

给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。

方法一 暴力法[超出时间限制]

思路

直接for循环找第一个错误版本。

代码

const solution = function(isBadVersion) {
return function firstBadVersion (n) {
for (let i = 1; i < n; i++) {
if (isBadVersion(i)) {
return i;
}
}
return n;
}
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    该方法需要遍历每一个元素,需要耗费O(n)O(n)时间,当遇见版本特别多的时候O(n)的时间,因此改方法时间复杂度为O(n)O(n)

  • 空间复杂度:O(1)O(1)

    该方法没有申请额外的空间,所以空间复杂度为O(1)O(1)

方法二 二分法

思路

前一种方法需要遍历每一个元素,这样如果元素特别多的时候会耗时过多,这个时候通过二分法也就是折半法(有序数组中查找特定元素的搜索算法)来查找元素。

二分法思路:

  1. 首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。

  2. 如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤(1)的操作。

  3. 如果某一步数组为空,则表示找不到目标元素。

    这样可以避免无差别遍历降低遍历耗时。

详解

  1. 确定数组左边边界值和右边边界值,找到边界值的中间值

  2. 比较中间值是否是错误版本,如果是则右边边界值=中间值-1,再找中间值比较。如果不是错误版本则左侧边界值=中间值+1,再找左侧值和右侧值之间的中间值比较,这样重复下去

  3. 当左侧边界值>右侧边界值得时候,说明右侧已经全是错误版本了,当前左侧的值就是临界值

代码

const solution = function(isBadVersion) {
return function firstBadVersion (n) {
let left = 1;
let right = n;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (isBadVersion(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}

复杂度分析

  • 时间复杂度为: O(log2(n))O(\log_2(n))

    对于n个元素的情况(去掉常数)

    第一次二分:n/2n/2

    第二次二分:n/22=n/4n/2^2= n/4、......

    m次二分:n/(2m)n/(2^m)

    在最坏情况下是在排除到只剩下最后一个值之后得到结果,所以为n/(2m)n/(2^m)=1,得到 2m=n2^m=n

    所以时间复杂度为:O(log2(n))O(\log_2(n))

  • 空间复杂度: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:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

方法一 二分查询最大最小值

思路

先算出 数组中最大最小值,利用 indexOf 计算之后要旋转位置,然后二分计算目标 target 位置

详解

  1. 计算数组中的最大最小值

  2. 定义变量,数组长度等

  3. 目标值大于数组最后一位时,数组查询位置从 0 到数字中在最大位置

  4. 目标值小于等于数组最后一位时,数组查询位置从数组中最小值的位置开始,到数组的最后一位,3.4 两部为了定位数组查询区间

  5. 循环二分查询,计算定位数组的中间值,数组的值等于目标查询结束

  6. 不等于的情况,如果目标大于中间值,则定位数组最小值等于中间值+1,目标小于中间值,则定位数组中最大值等于中间值-1,继续循环查询即可,知道定位数组查询完毕,没有结果的话,返回 -1 代表不存在

代码

const search = function (nums, target) {
const min = Math.min.apply(null, nums);
const max = Math.max.apply(null, nums);
const len = nums.length;
let pos;
let lo;
let hi;
let mid;
if (target > nums[len - 1]) {
pos = nums.indexOf(max);
lo = 0;
hi = pos;
} else {
pos = nums.indexOf(min);
lo = pos;
hi = len - 1;
}
while (lo <= hi) {
mid = Math.ceil((lo + hi) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
};

复杂度分析:

  • 时间复杂度:O(log(n))O(log(n))

    过程会最多遍历一遍数组

  • 空间复杂度:O(1)O(1)

    只产生一次临时变量存储

方法二 二分查询中间数

思路

根据数组的中间数和左右节点的大小对比,来确定升序部分的位置,然后用二分法查询目标节点在数组中的位置

详解

  1. 计算数组长度,数组为0 直接返回-1

  2. 定义左右值分别为数组第一个和最后一个的下标

  3. 中间下标值为最大最小值的平均数

  4. 如果数组中间数等于目标直接返回下标

  5. 数组的中间值小于数组最后一个值,后半部分还处于升序,如果目标值在这部分数组中,则左下标等于中间值+1,代表目标值在后半部分数组,反着重新定义右下标为中间值-1,目标在前半数组

  6. 数组中间值大于数组最后一个值,代表前半部分数组处于升序,如果目标在前半数组中,右标更新为中间值-1,反之,左下标更新为中间值+1

  7. 二分查询到最后没找到目标值,则返回 -1 代表不存在

代码

const search = function(nums, target) {
if(nums.length === 0){
return -1;
}
let left = 0;
let right = nums.length - 1;
let mid;
while(left <= right){
mid = parseInt((left + right) / 2);
if(nums[mid] === target){
return mid;
} else if(nums[mid] < nums[right]) {
if(nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
if(nums[left] <= target && target < nums[mid]){
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
};

复杂度分析

  • 时间复杂度:O(log(n))O(log(n))

    过程会最多遍历一遍数组

  • 空间复杂度:O(1)O(1)

    只产生一次临时变量存储