LeetCode268——缺失数字

青旅半醒 2022-03-12 11:14 206阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/missing-number/][https_leetcode-cn.com_problems_missing-number]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：数学

### 思路一：开一个空间大一位的数组来记录每个数字出现与否 ###

时间复杂度和空间复杂度均是O(n)，其中n为数组的长度。

JAVA代码：

public class Solution {
        public int missingNumber(int[] nums) {
            int[] temp = new int[nums.length + 1];
            Arrays.fill(temp, -1);
            for (int i = 0; i < nums.length; i++) {
                temp[nums[i]] = nums[i];
            }
            for (int i = 0; i < temp.length; i++) {
                if (-1 == temp[i]) {
                    return i;
                }
            }
            return -1;
        }
    }

LeetCode解题报告：

![20190305210558318.jpg][]

### 思路二：在原数组中交换，交换原则是第i的位置放数字i ###

时间复杂度是O(n)，其中n为数组的长度。空间复杂度是O(1)。

JAVA代码：

public class Solution {
        public int missingNumber(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                int temp = i;
                while (temp != nums[temp] && nums[temp] != nums.length) {
                    swap(nums, temp, nums[temp]);
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (i != nums[i]) {
                    return i;
                }
            }
            return nums.length;
        }
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

LeetCode解题报告：

![20190305210739509.jpg][]

### 思路三：求\[1, n\]间的数字和，再求出数组中的元素和，两者之差即为缺少的数字 ###

时间复杂度是O(n)，其中n为数组的长度。空间复杂度是O(1)。

JAVA代码：

public class Solution {
        public int missingNumber(int[] nums) {
            int sum1 = (1 + nums.length) * nums.length / 2;
            int sum2 = 0;
            for (int num : nums) {
                sum2 += num;
            }
            return sum1 - sum2;
        }
    }

LeetCode解题报告：

![20190305210833567.jpg][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_missing-number]: https://leetcode-cn.com/problems/missing-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220312/98dd4e1d62ad4a9e80603c4e23560734.png
[20190305210558318.jpg]: /images/20220312/ddc94c97bdbf468a8ef08982397ff73d.png
[20190305210739509.jpg]: /images/20220312/e25978828593492196dde80adb44bf1c.png
[20190305210833567.jpg]: /images/20220312/ee9c7022b4fc4f5f9d12080ba71b2772.png