leetcode 33,81

ゝ一纸荒年。 2023-06-15 14:30 6阅读 0赞

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

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

class Solution {
        
        public int search(int[] nums, int target) {
        
            // 为啥旋转数组也能二分
            // 二分的精髓就是 排除法
            // 首先，部分序列递增有序能二分
            // 分mid  再判断左右
            // 分Mid 的策略是什么  怎么时候去掉左边  什么时候去掉右边
            if (nums.length == 0)return -1;
            int l = 0;
            int r = nums.length-1;
    
            while (l < r) {
        
                int m = (l + r) >>> 1;
                if (nums[m] == target)
                    return m;
                else if (nums[m] > nums[r]) {
        
                    if (nums[l] <= target && target < nums[m]) {
        
                        r = m -1;
                    } else {
        
                        l = m + 1;
                    }
                } else if (nums[m] < nums[r]) {
        
                    if (nums[m] < target && target <= nums[r]) {
        
                        l = m + 1;
                    }else {
        
                        r = m -1;
                    }
                }
            }
            if (nums[l] == target)
                return l;
            else return -1;
        }
    }

leetcode 81  
在31题的基础上，增加数组的重复元素  
只要判断重复元素，right = right-1即可。

class Solution {
        
        public boolean search(int[] nums, int target) {
        
            if (nums.length == 0)
                return false;
            int l = 0;
            int r = nums.length-1;
    
            while (l < r) {
        
                int mid = (l + r) >>> 1;
                if (nums[mid] > nums[r]) {
        
                    // 前部分递增
                    if (nums[l] <= target && target <= nums[mid]) {
        
                        r = mid;
                    } else {
        
                        l = mid + 1;
                    }
    
                } else if (nums[mid] < nums[r]) {
        
                    // 后部分递增
                    if (nums[mid] <= target && target <= nums[r] ) {
        
                        l = mid;
                    } else {
        
                        r = mid - 1;
                    }
                } else {
        
                    if ( nums[mid] == target)
                        return true;
                    else 
                        r = r - 1;
                }
    
            }
            if (nums[l] == target) {
        
                return true;
                }
                return false;
        }   
    }