Java Two methods, using sign and swap


  • 2

    Method 1 is to put each element k to the k-1th position unless the k-1th is already occupied by k. In that case we know k is a duplicate. In a second pass, we look for the ith position where its value is not i+1, we know i+1 is the missing value.

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    
        public int[] findErrorNums(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                while (nums[nums[i]-1] != nums[i]) {
                    swap(nums, i, nums[i]-1);
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != i+1) return new int[]{nums[i], i+1};
            }
            return null;
        }
    

    Method 2: when we encounter a value k, we set the k-1th element negative. If k-1th is already negative we know k is the duplicate. In the second pass we look for ith position where it's value is positive so we know i+1 is the missing one.

        public int[] findErrorNums(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                while (nums[nums[i]-1] != nums[i]) {
                    swap(nums, i, nums[i]-1);
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != i+1) return new int[]{nums[i], i+1};
            }
            return null;
        }
    

  • 0
    This post is deleted!

Log in to reply
 

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