My C++ solution with O(1) space and O(nlogn) time


  • 0
    C
    class Solution {
     public:
      int findDuplicate(vector<int>& nums) {
        const int n = static_cast<int>(nums.size()) - 1;
        int left = 1;
        int right = n + 1;
        while (left < right - 1) {
          int mid = (left + right) >> 1;
          int count[2] = {0};
    
          for (size_t i = 0; i < nums.size(); ++i) {
            if (nums[i] >= left && nums[i] < mid) {
              ++count[0];
            } else if (nums[i] >= mid && nums[i] < right) {
              ++count[1];
            }
          }
          if (count[0] > mid - left) {
            right = mid;
          } else {
            left = mid;
          }
        }
        return left;
      }
    };

  • 0
    C
    This post is deleted!

Log in to reply
 

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