Leetcode -645- Collection of errors

[Blog link]

The path to learning at 🐔

The nuggets home page

[Topic Description

The set S contains the data from1Integers up to n. Unfortunately, because of a data error, one number in the set copies the value of another number in the set, causing the set to lose a number and have a duplicate number. Given an array nums represents the result of an error in set S. Find the duplicate integers, find the missing integers, and return them as an array. The sample1: Input: nums = [1.2.2.4] output: [2.3] example2: Input: nums = [1.1] output: [1.2] :2 <= nums.length <= 104 
 1 <= nums[i] <= 104Related Topics Bit operation array hash table sort 👍189 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

** Idea 1: Hash storage + double traversal

public int[] findErrorNums(int[] nums) {
            int[] temp = new int[nums.length + 1];
            int index = 0, res = 0;
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                if (set.contains(nums[i])) {
                    index = nums[i];
                }
                set.add(nums[i]);
                temp[nums[i]] = nums[i];
            }
            for (int i = 1; i < temp.length; i++) {
                if (temp[i] == 0) { res = i; }}return new int[]{index, res};
        }
Copy the code


Time complexity O ( n ) Time complexity O(n)

Idea 2: The optimization of idea 1

  • Reduce set storage by repeating elements in an array
public int[] findErrorNums(int[] nums) {
            int[] temp = new int[nums.length + 1];
            int index = 0, res = 0;
            for (int i = 0; i < nums.length; i++) {
                temp[nums[i]]++;
            }
            for (int i = 1; i < temp.length; i++) {
                if (temp[i] == 0) {
                    res = i;
                }
                if (temp[i] == 2) { index = i; }}return new int[]{index, res};
        }
Copy the code


Time complexity O ( n ) Time complexity O(n)

Idea 3: Math

  • The normal sum of non-repeating elements is the arithmetic sequence sum total
  • Repeating elements through an array
  • Sum of all – non-repeating elements and are repeating elements
  • Target and – non-repeating elements and are missing elements
public int[] findErrorNums(int[] nums) {
            int n = nums.length;
            int total = (1 + n) * n / 2;
            int[] temp = new int[n + 1];
            int sum = 0, set = 0;
            for (int x : nums) {
                sum += x;
                if (temp[x] == 0) set += x;
                temp[x] = 1;
            }
            return new int[]{sum-set, total-set};
        }
Copy the code


Time complexity O ( n ) Time complexity O(n)

Idea 4: Bucket sorting

  • Insert the corresponding element I into numS [i-1]
  • And then I go through it once and find the non-corresponding element
  • Can save storage space
public int[] findErrorNums(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                // Loop until you find the corresponding element
                while(nums[i] ! = i +1 && nums[nums[i] - 1] != nums[i]) {
                    swap(nums, i, nums[i] - 1); }}int a = -1, b = -1;
            for (int i = 0; i < n; i++) {
                if(nums[i] ! = i +1) {
                    a = nums[i];
                    b = i == 0 ? 1 : nums[i - 1] + 1; }}return new int[]{a, b};
        }

        private void swap(int[] nums, int l, int r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
Copy the code

Time complexity O(n), space complexity O(1)