Leetcode 33:搜索旋转排序数组

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [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

解题思路

​ 根据题目时间复杂度的要求，只能是二分搜索。关键就是判断什么时候应该向左搜索，什么时候应该向右搜索。归纳观察可知，当中间的数大于head时，左边是降序的；小于tail时，右边是降序的。

代码

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length- 1;
        int res = -1;
        
        while( lo <= hi){
            int mid = lo + (hi -  lo)/ 2;
            if(nums[mid] == target) {
                res = mid;
                break;
            }
            
            if(nums[mid] >= nums[lo]){
                if(target < nums[mid] && target >= nums[lo]) hi = mid - 1;
                else lo = mid + 1;
            }
            else{
                if(target > nums[mid] && target <= nums[hi]) lo = mid+ 1;
                else hi = mid -1;
            }
    }
        
        return res;
    }
}

Leetcode 540 :有序数组中的单一元素

题目描述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例 2:

输入: [3,3,7,7,10,11,11] 输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

解题思路

这题容易和Leetcode 136. Single Number混淆，注意题目的要求是O(log n)的时间复杂度，也就是只能用二分查找或类似的方法。这题多的信息就是数组是有序的，所以我们要充分利用已知信息，找到调整左右边界的关键。

这个主要基于这样一个规律：如果nums[mid] ==nums[mid],在mid为偶数的时候，答案一定在后半段，在mid为奇数的时候，答案一定在前半段。

参考答案

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        
        while(lo < hi ){
            int mid = lo + (hi - lo)/2;
            if( mid % 2 == 1){
                if(nums[mid]== nums[mid - 1]) {
                    lo = mid + 1;
                }
                else{
                    hi = mid -1;
                }
            }
            else{
                if(nums[mid] == nums[mid -1]){
                    hi = mid -2;
                }
                else{
                    lo = mid;
                }
            }
        }
        
        return nums[hi];
    }
}

Leetcode 1060:有序数组中的缺失元素

题目描述：

给出一个有序数组 A，数组中的每个数字都是 独一无二的，找出从数组最左边开始的第 K 个缺失数字。

示例 1：

输入：A = [4,7,9,10], K = 1 输出：5 解释： 第一个缺失数字为 5 。 示例 2：

输入：A = [4,7,9,10], K = 3 输出：8 解释： 缺失数字有 [5,6,8,…]，因此第三个缺失数字为 8 。 示例 3：

输入：A = [1,2,4], K = 3 输出：6 解释： 缺失数字有 [3,5,6,7,…]，因此第三个缺失数字为 6 。

提示：

1 <= A.length <= 50000 1 <= A[i] <= 1e7 1 <= K <= 1e8

解题思路

简单的数学计算，找到缺失数字所在的区间，然后再根据前一个数算出来。

参考答案

class Solution {
    public int missingElement(int[] nums, int k) {
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i+ 1] - nums[i] - 1 >= k){
                return nums[i] + k;
            }
            k = k - (nums[i+ 1] - nums[i] - 1);
        }
        
        return nums[nums.length - 1] + k;
    }
}

其实这题还可以用二分查找的思路求解。