No sorting, O(N) solution with no extra space


  • 0
    B

    Note: This is an AC solution, but not correct. I violated the "treat the list as read-only". Otherwise it's correct.

    Algorithm: Just go through the array, treat every absolute value as an index. Just flip the nums[index] to negative.

    If the nums[index] is already negative, then it means it has already been flipped. Then "index" is the duplicated number.

    e.g.

    5 2 1 3 4 5 6

    We go through the numbers: (x) is the current one, [y] is the flipped one

    (5) 2 1 3 4 [-5] 6

    5 (2) [-1] 3 4 -5 6

    5 [-2 ] (-1) 3 4 -5 6

    5 -2 -1 [(-3)] 4 -5 6

    5 -2 -1 -3 [(-4)] -5 6

    5 -2 -1 -3 -4 [(5)] 6 <--- Now the 5 is positive, means it has already been flipped, the index is duplicated

    Python Code

    class Solution(object):
        def findDuplicate(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            for i in range(len(nums)):
                index = abs(nums[i])
                nums[index] *= -1
                if nums[index] > 0: return index
    

    C++ Code

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            for ( int i = 0; i < nums.size(); ++i )
            {
                int index = abs(nums[i]);
                nums[index] *= -1;
                if ( nums[index] > 0 ) return index;
            }
        }
    };

  • 0
    S

    Note:
    1.You must not modify the array (assume the array is read only).


  • 0
    V

    Besides the read-only issue, it happens to work in the example above because the duplicated value 5 happens to be in the 5th of the array, which is not guaranteed.


  • 0
    B

    No, the only problem is I ignored the read-only. Let's say 5 into 1. Runs:
    (5) 2 1 3 4 [-1] 6

    5 (2) [-1] 3 4 -1 6

    5 [-2 ] (-1) 3 4 -1 6

    5 -2 -1 [(-3)] 4 -1 6

    5 -2 -1 -3 [(-4)] -1 6

    5 [2] -1 -3 -4 (1) 6 <--- Now the 2 is positive, means it has already been flipped, the index 1 is duplicated


  • 0
    R

    This is equivalent to use a hashtable. Because the range the number are fixed, so we could just use an array as a hashtable. In your case, it is a table of sign.


  • 0
    C

    This solution is to use the original array as placeholder that records the presence of each element (which uses basically O(n) space).
    The essence of this problem is how to do the above in O(1) space rather than O(n) while maintaining the speed.
    This is nonetheless a smart algorithm. Thanks for sharing.


Log in to reply
 

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