Java O(n) Time, O(1) Space. Similar to find missing number. Simulating hash function.


  • 0
    R

    This solution is very similar to the other problem. Pretty much, we are leveraging the index to find out the missing number.

    
        public int findDuplicate(int[] n) {
                if (n == null || n.length == 0) return 0;
                for (int i = 0; i < n.length; i++)
                {
                    if (n[Math.abs(n[i])-1] > 0) n[Math.abs(n[i])-1] = -n[Math.abs(n[i])-1];
                    else return Math.abs(n[i]);
                }
            
                return 0; //Will never comes to here
          }

Log in to reply
 

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