81. Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

思路:

这题好像是33题的follow up。

增添了各个元素可能相等的条件。

没做出来。

如果考虑在上一题的思路,先寻找找出二分点,在二分两端数字。如果遇到 nums[mid]==nums[l]那就需要遍历确定哪边是相等的,巴拉巴拉……,多了一堆条件设置和条件判断。

跳出这层,能不能直接在二分搜索呢?

Read more

4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays - 第K大 + 二刷

思路:

将查找中位数扩大为更广义的解法:求解第$K$位的数字。每次在A,B两个数组中划分出两个k/2个元素,并排除划分出的最后一个数字比较小的数组,然后减去对应的排除的数组的数字个数,更新$K$值。直到$K==1$,或者其中一个数组为空。

详细题解如下

Read more

81. Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

思路:

这题好像是33题的follow up。

增添了各个元素可能相等的条件。

没做出来。

如果考虑在上一题的思路,先寻找找出二分点,在二分两端数字。如果遇到 nums[mid]==nums[l]那就需要遍历确定哪边是相等的,巴拉巴拉……,多了一堆条件设置和条件判断。

跳出这层,能不能直接在二分搜索呢?

Read more

面试题53 - II. 0~n-1中缺失的数字

好菜啊,二分都不会了写了出了三个bug,还好检查的快。 Leecode的无调试debug还是相当锻炼人的。

简单思路:hash一下每个数据,找出空白值即可。

二分思路:依据前半部分有nums[i] == i的性质,和后半部分nums[i] != i的不同可以二分数据,从而找出错位的第一个数据。但是错位的数据不一定是缺少的数据,如果i==len(nums)就可能有缺失数据n−1n−1的可能性。

cpp
class Solution {
public:
//     int missingNumber(vector<int>& nums) {
//         int len = nums.size();
//         int *hs = new int[len + 1];
//         //未初始化,或者说函数中new的数组初始状态非零
//         memset(hs,0, sizeof(int) * (len + 1) );
//         for(int i = 0;i < len ; ++i) hs[nums[i]] = 1;
//         for(int i = 0;i < len + 1; ++i)
//             if( hs[i] == 0) 
//                 return i; 
//         return 0;
//     }
// };

    int missingNumber(vector<int>& nums) {
        int right = nums.size() - 1, left = 0, mid = right;
        //bug1 边界情况
        if(nums[right] == right) return right + 1;
        while(left < right){
            mid = (left + right) / 2;
         //bug2 二分错误
            if( nums[mid] == mid )
                left = mid + 1;
            else if( nums[mid] != mid)
                right = mid;
        }
        //bug3 mid值没被更新, 而 left 和 right 都可以
        return left;
  w
    }
};