解法:排序数组,第一时间想到的应该是二分
但这题二分细节较多,思路需要捋清楚,除了对比二分的位置,还需要考虑需要旋转后的阶段性有序。
代码:这里有两个讨论点,可以看到对比时,使用的是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条评论