Is there a solution faster than O(nlogn) ?


  • 0
    B

    This problem is quite easy if there are not so many requirements.
    And the reqirement "Array must not be modified" costs me much time to think out
    the following solution eventually much time.

    Any more faster solutions ? If yes, pls tell me, thx very very much.

    int _duplicated (const int *nums, int numsSize, int start, int end)
    {
        int n, i, m, mc;
        
        if (start == end) return start;
        m = (start + end) >> 1;
        for (i = n = mc = 0; i < numsSize; ++i) {
            if (nums[i] == m) {
                ++mc;
            } else if (nums[i] > m && nums[i] <= end) {
                ++n;
            }
        }
        if (mc > 1) return m;
        if (n > end - m) return _duplicated (nums, numsSize, m + 1, end);
        else return _duplicated (nums, numsSize, start, m - 1);
    }
    int findDuplicate(int* nums, int numsSize)
    {
        return _duplicated (nums, numsSize, 1, numsSize - 1);
    }

  • -1
    S
    This post is deleted!

Log in to reply
 

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