Binary-Search C++ with O(nlogn) time and O(1) space complexity


  • 0
    5
    class Solution {
    public:
        int cmp(vector<int>& nums, int val, int& low, int& up) {
            int t = 0;
            for (vector<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
                if (*it == val) {
                    t++;
                } else if (*it > val) {
                    up++;
                } else {
                    low++;
                }
            }
            return t;
        }
        
        int findDuplicate(vector<int>& nums) {
            int n = nums.size() - 1;
            int l = 1, r = n;
            while (l < r) {
                int mid = (l + r) / 2, low = 0, up = 0;
                int cnt = cmp(nums, mid, low, up);
                if (cnt > 1) {
                    return mid;
                }
                if (low >= mid) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return l;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.