Is sort satisfy the request?


  • -4
    T
    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
          sort(nums.begin(), nums.end());
          for (int i = 0;i<nums.size();i++)
            if (nums[i]==nums[i+1])
              return nums[i];
        }
    };
    

    This is my solution. Sort first, and then compare between num, once they are the same, answer is found.

    It seems satisfy the request.

    What's more, I don't understand the request that " Your runtime complexity should be less than O(n2)", I think its wrong? It should be O(nlgn)?


  • 2
    T

    Hi, One of the requirement was to not modify the array. By sorting it you modified the array. If you make a copy array and sort that, then you will be using O(N) space, which violate the second requirement of using constant space. So you have to come up with a method under these two limitations.


Log in to reply
 

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