题目链接:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
个人题解:索引法
代码:
class Solution { public: int findRepeatNumber(vector<int>& nums) { int i=0,n=nums.size(); while(i<n){ if(nums[i]==i) { i++; continue; } if(nums[nums[i]]==nums[i]) return nums[i]; swap(nums[i],nums[nums[i]]); } return -1; } };
结果:
题目链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ (其实挺好奇为什么他的题目的英文描述是拼音hhh)
个人题解:二分查找即可,时间复杂度 \(O(logN)\) (可以调用函数也可以手写)
代码:
class Solution { public: int search(vector<int>& nums, int target) { return upper_bound(nums.begin(), nums.end(), target) - lower_bound(nums.begin(), nums.end(), target); } }; class Solution { public: int search(vector<int>& nums, int target) { if(!nums.size()) return 0; int le=0,ri=nums.size()-1; while(le<ri){ int mid=ri+le>>1; if(nums[mid]>=target) ri=mid; else le=mid+1; } if(nums[ri]!=target) return 0; int idx=le; le=0,ri=nums.size()-1; while(le<ri){ int mid=ri+le+1>>1; if(nums[mid]<=target) le=mid; else ri=mid-1; } int idx1=ri; return idx1-idx+1; } };
结果:(第一张图调用函数,第二张图手写,手写快了一点)
题目链接:https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
个人题解:二分查找,如果数字和下标一样则继续,反之退出
代码:
class Solution { public: int missingNumber(vector<int>& nums) { int i=0,j=nums.size()-1; while(i<=j){ int mid=i+j>>1; if(nums[mid]==mid) i=mid+1; else j=mid-1; } return i; } };
结果: