leetcode排序和搜索常见面试算法题

什么叫ARTS？

每周完成一个ARTS：

1. Algorithm：每周至少做一个 leetcode 的算法题
2. Review：阅读并点评至少一篇英文技术文章
3. Tip：学习至少一个技术技巧
4. Share：分享一篇有观点和思考的技术文章

作者：陈皓
链接：https://www.zhihu.com/question/301150832/answer/529809529
来源：知乎

_Merge Sorted Array

给两个有序数组排序，排序后合并到数组1中。

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

方法一

1. 采用双指针法，同时遍历两个数组。
2. 比较遍历到的数，将较小的数提取到临时数组，临时指针++，较小数组遍历指针++，如果相等，将这个等数提取到临时数组，需要存两次，同时两个数组的遍历指针++。
3. 直到有一方遍历完成，将另外未遍历完的直接插入临时数组。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=0,j=0;
        vector<int> temp;
        while(i<m && j<n) {
            if(nums1[i]==nums2[j]) {
                temp.push_back(nums1[i]);
                temp.push_back(nums1[i]);
                i++;
                j++;
            } else if(nums1[i]<nums2[j]) {
                temp.push_back(nums1[i]);
                i++;
            } else {
                temp.push_back(nums2[j]);
                j++;
            }
        }
        for(;i<m;i++)
            temp.push_back(nums1[i]);
        for(;j<n;j++)
            temp.push_back(nums2[j]);
        nums1=temp;
    }
};

方法二

1. 排完序的数组1总共有m+n位，从两数组末尾m,n处同时遍历数组，将大的数存入数组1的m+n末尾，大的数存入后还需要移动指针，相等的数需要存入两次，两个数组的指针都需要移动一次。
2. 遍历完成，再将剩下未遍历完的数组补上到数组1的末尾。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1,j=n-1,k=m+n-1;
        while(i>=0 && j>=0) {
            if(nums1[i]==nums2[j]) {
                nums1[k--]=nums1[i--];
                nums1[k--]=nums2[j--];
            } else if(nums1[i] > nums2[j]) {
                nums1[k--]=nums1[i--];
            } else {
                nums1[k--]=nums2[j--];
            }
        }
        while(i>=0)
            nums1[k--]=nums1[i--];
        while(j>=0)
            nums1[k--]=nums2[j--];
    }
};

First Bad Version

找到第一个坏版本

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

方法一

1. 采用折半查找，先找一半的那个数是否是坏版本，如果不是则向前找一半，如果是，则向后找一半。折半查找的方法为定义一个low，high，不断缩减范围，注意跳出循环的条件。
2. 直到无法寻找。

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int low=1, high=n, mid=1;
        while(high>low) {
            mid=low+(high-low)/2;
            if(isBadVersion(mid)) {
                high=mid;
            } else {
                low=mid+1;
            }
        }
        return high;
    }
};

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int low=0, high=n;
        while(high-low>1) {
            int mid=low+(high-low)/2;
            if(isBadVersion(mid)) {
                high=mid;
            } else {
                low=mid;
            }
        }
        return high;
    }
};