Java 10ms (beats 100% @ 2017-07-23 15:56:14) O(N) time O(1) space


  • 0

    This is a technique that is extensible to most array problems where the value domain equals the index domain (possibly with shift difference of 1) : keep the flags directly in the input array.

    Negate an entry to mark that this entry has been seen before. If so discovered, duplicate found. At the end 1 extra pass to find the only number that is positive due to lack of occurrence.

    public class Solution {
        public int[] findErrorNums(int[] nums) {
            int[] res = new int[2];
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                int index = Math.abs(nums[i]) - 1;
                if (nums[index] < 0) {
                    res[0] = index + 1;
                } else {
                    nums[index] = - nums[index];
                }
            }
            for (int i = 0; i < n; i++)
                if (nums[i] > 0)
                    res[1] = i + 1;
            return res;
        }
    }
    

Log in to reply
 

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