There are bugs in the test system


  • -1
    S
    // binary search
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size();
        int m = 0, c = 0;
        while (l <= r) {
            m = (l + r) / 2;
            
            c = 0; // number less or equal to m
            for (int x : nums) {
                if (x <= m) ++c;
            }
            
            if (c > m) r = m - 1; // duplicate number must located in [0, m-1]
            else l = m + 1;       // duplicate number must located in [m+1, r]
        }
        
        return l;
    }

  • 0

    I think you posted the wrong code. I don't see any way that this code doesn't TLE for that input, and I just tried it and it did TLE.


  • 0
    S

    @StefanPochmann, I have updated the code (which is not right), and it pass the judge system!


  • 0

    I believe it's actually correct now. Do you have an input that it fails?

    With the invariant being that the correct answer lies in [l,r+1], the invariant is true at start (although r is two higher than necessary) and after each iteration and thus at the end. And you stop with l=r+1 and thus have exactly one number in [l,r+1] and it's the correct answer. No?


Log in to reply
 

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