合并两个有序数组

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
初始化 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]

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
提示:
  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[i] <= 109
相关标签:数组 双指针 排序
#pragma once
#includeusing std::vector;

class Solution {
public:

    void merge(vector& nums1, int m, vector& nums2, int n) {
        /*三指针
        
        std::vectorvec(m + n);         //定义一个数组vec,size=m+n,用来暂时存储合并后的俩个数组

        int i = 0;
        int j = 0;
        int k = 0;
        while (i != m && j != n) {          //遍历比较nums1和nums2两个数组,按升序加入到vec中。循环退出条件即任一数组全部遍历完
            if (nums1[i] <= nums2[j]) { vec[k++] = nums1[i++]; } else { vec[k++] = nums2[j++]; } } if (i == m) { //循环结束可能只是其中一个数组遍历完,所以还有另一个数组还未遍历完,可知只需将其剩余部分元素加入到vec后即可 while (j != n) { vec[k++] = nums2[j++]; } } else { while (i != m) { vec[k++] = nums1[i++]; } } nums1 = vec; //最后将临时数组元素复制到nums1即可 */ //逆向三指针(不需要额外的临时数组,直接在nums1上操作) int i = m - 1; int j = n - 1; int k = m + n - 1; while (i >= 0 && j >= 0) {              //从后往前遍历比较,将大的放在nums1后面,从后往前找大的
            if (nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            }
            else {
                nums1[k--] = nums2[j--];
            }
        }

        if (i < 0) { while (j >= 0) {
                nums1[k--] = nums2[j--];
            }
        }
        else {
            while (i >= 0) {
                nums1[k--] = nums1[i--];
            }
        }

    }
};

第一个错误的版本

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

输入:n = 1, bad = 1
输出:1
提示:
  • 1 <= bad <= n <= 231 - 1
相关标签:二分查找 交互
#pragma once
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {     bool isBadVersion(int version);     //在官方内部     public:         int firstBadVersion(int n) {         /*by myself(递归)
        if (isBadVersion(n) != true) {
            return n + 1;
        }
        return firstBadVersion(n - 1);
        */         //by myself(二分查找)         int left = 0;         int right = n;         while (left <= right) {             int mid = left + (right - left) / 2;             //注:这里将的mid等于中间位置左边的值,所以最终返回的结果是left; 还有就是尽量不要写成 mid=(left+right)/2 的形式(因为 left+right 可能导致溢出)              if (isBadVersion(mid) == true) {                 //如果mid当前是错误版本,则isBadVersion(mid)返回true,如果要找到第一个BadVersion,应该在左半区间(left,mid-1)继续查找,所以                 right=mid-1 right = mid-1;             }              else {                 left = mid + 1;                 //否则表示mid当前是正确版本,在 left<=right之前 应该继续在右半区间查找第一个BadVersion,采取包夹一样的策略最终找到FirstBadVersion                              }         }         return left;              }
}
;