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

  • 0

    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.