81. 搜索旋转排序数组 II
33. 搜索旋转排序数组
代码一样:
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
示例 1: 输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true 示例 2: 输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false
class Solution { public: bool search(vector<int>& nums, int trget) { int n = nums.size(); if( n== 0) return false; int l = 0, r = n -1; while( l < r){ int m = l + (r-l)/2; //左边是排好序的序列: if(nums[m] > nums[l]) //target在左还是右: if(target >= nums[l] && target <= nums[m]) r = m; else l = m+1; // 右边是排好序的序列: else if(nums[m] < nums[l]) if(target > nums[m] && target <= nums[r]) l = m+1; else r = m; else// 如果相等,不能区分左边还是右边 if(nums[m] == target) return true; else l++; } //最后还要判断: return nums[l] == target; } };
162. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。
数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞
这题的数学思想:
如果nums[i] > nums[i+1],则在i之前一定存在峰值元素
如果nums[i] < nums[i+1],则在i+1之后一定存在峰值元素
class Solution { public: int findPeakElement(vector<int>& nums) { int l = 0, r = nums.size() - 1; while( l < r){ int m = l + (r-l)/2; if(nums[m] <= nums[m+1]) l = m+1; else r = m; } return l; } };
287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
说明:
不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字,但它可能不止重复出现一次
class Solution { public: int findDuplicate(vector<int>& nums) { int n = nums.size(); //时间复杂度为n*logn;二分地猜测可能的数;每次遍历一遍数组来确认左边还是右边; int l = 1, r = n-1; while(l < r){ int m = l + (r-l)/2; int cnt = 0; for(auto x: nums) if(x <= m) cnt++; //如果数量大于m,则搜索区间[l,m] if(cnt > m) r = m; //否则 [m+1,r] else l = m+1; } return l; } };