LeetCode 33. 搜索旋转排序数组

2024-01-10 12:13:01

搜索旋转排序数组

整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

方法一、二分查找

题目时间要求为O(logn),因此,首先想到的是用二分查找。由于有序数组被旋转了,因此我们需要找出规律和定理:

  • 定理一:每次二分都会至少存在一个顺序区间
  • 定理二:只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。
  • 定理三:判断顺序区间还是乱序区间,只需要对比 left 和 right 是否是顺序对即可,left <= right表示顺序区间,否则乱序区间。

复杂度分析
时间复杂度:O(logn),n为nums数组的容量,本质就是二分查找的时间复杂度
空间复杂度:O(1),只需要常量的空间存储变量

Swift

func search(_ nums: [Int], _ target: Int) -> Int {
        
        let cnt = nums.count
        var left = 0, right = cnt - 1
        
        while left <= right {
            let mid = (left + right) >> 1
            
            if target == nums[mid] {
                return mid
            }
            
            if nums[left] <= nums[mid] {//左侧严格升序
                if target >= nums[left] && target < nums[mid] {//值是否在有序区间内
                    right = mid - 1
                }else {
                    left = mid + 1
                }
            }else {//右侧严格升序
                if target > nums[mid] && target <= nums[right] {//值是否在有序区间内
                    left = mid + 1
                }else {
                    right = mid - 1
                }
            }
        }
        
        return -1
    }

OC

-(NSInteger)search:(NSArray <NSNumber *>*)nums target:(NSInteger)target {
    NSInteger cnt = nums.count;
    
    NSInteger left = 0, right = cnt-1;
    
    while (left <= right) {
        NSInteger mid = (left + right) >> 1;
        
        if (target == [nums[mid] integerValue]) {
            return mid;
        }
        
        //用到了定理:每次二分都会至少存在一个顺序区间
        if ([nums[mid] integerValue] >= [nums[left] integerValue]) {//左侧严格升序
            if(target >= [nums[left] integerValue] && target < [nums[mid] integerValue]) {//target是否在升序区间内
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }else {//右侧严格升序
            if (target > [nums[mid] integerValue] && target <= [nums[right] integerValue]) {//target是否在升序区间内
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

文章来源:https://blog.csdn.net/zzl819954692/article/details/135498429
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。