抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

Leetcode 33. 搜索旋转排序数组

33. 搜索旋转排序数组

解法:排序数组,第一时间想到的应该是二分

但这题二分细节较多,思路需要捋清楚,除了对比二分的位置,还需要考虑需要旋转后的阶段性有序。

代码:这里有两个讨论点,可以看到对比时,使用的是nums[0]nums[nums.size -1],我在提交时先后将 nums[num.size-1]换成了nums[r],nums[0]换成了 nums[l],在 leetcode 中测试用例中均可通过。

时间复杂度: O(log n) 空间复杂度:O(1)

这时候我的脑子告诉我:“算了吧,这我也捋不清”,然后我去看下了其他评论,都差不多是把官方的思路换了个写法,明显可以感觉到的是,使用[0]和[size – 1]会将范围放大,在更大的更复杂的样本会更可靠?日后水平提高再确认。

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        if (nums.isEmpty()) return -1
        if (nums.size == 1) {
            if (nums.first() == target) return 0 else -1
        }
        var l = 0
        var r = nums.size - 1
        while (l <= r) {
            val mid = l + (r - l) / 2
            if (nums[mid] == target) return mid
            if (nums[0] <= nums[mid]) {
                //左侧为有序
                if (nums[0] <= target && target < nums[mid]) {
                    //target 在[left,mid]这个有序范围内
                    r = mid - 1
                } else {
                    l = mid + 1
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.size - 1]) {
                    //如果右侧有序并在这个范围内
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
        }
        return -1
    }
}

0条评论

发表评论