C++ 12ms solution


  • 1
    M
    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int l = 1;
            int r = nums.size()-1;
            
            while (l < r) {
                int m = (l + r) / 2;
                int num = l-r+1;
                if (num % 2 == 0) {
                    int ln = 0;
                    int rn = 0;
                    for (int i : nums) {
                        if (r >= i && i > m) {
                            rn++;
                        } else if (m >= i && i >= l)  {
                            ln++;
                        }
                    }
                    
                    if (ln < rn) {
                        l = m+1;
                    } else {
                        r = m;
                    }
                } else {
                    int ln = 0;
                    int rn = 0;
                    for (int i : nums) {
                        if (r >= i && i >= m) {
                            rn++;
                        } else if (m > i && i >= l) {
                            ln++;
                        }
                    }
                    
                    if (ln+1 < rn) {
                        l = m;
                    } else {
                        r = m-1;
                    }
                }
            }
            
            return l;
        }
    };
    

Log in to reply
 

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