classSolution {public:intfindDuplicate(vector<int>& nums) {int low =1, high =nums.size() -1, cnt;while(low <= high) {int mid = low + (high - low) /2; cnt =0; // cnt number less than equal to midfor(int n : nums) {if(n <= mid)++cnt; } // binary search on leftif(cnt <= mid) low = mid +1;else // binary search on right high = mid -1; }return low; }};
Approach 4:
Important method , N Time + 1 Space
Marking the index
Basically we treat elements as index and
LEt say we get 4, we make nums[4] as -nums[4]
But duplicate element will cause double changes, will get caught
C++
classSolution {public:intfindDuplicate(vector<int>& nums) {int n =nums.size();for(int i =0; i < n; ++i){int idx =abs(nums[i]);if(nums[idx] <0)return idx;nums[idx] =-nums[idx]; }return n; }};