🌗 268. 丢失的数字

难度: 🌗

问题描述

---

解法 1 - 原地 hash

class Solution {
    public int missingNumber(int[] nums) {
        // 思路：
        // 遍历
        int len = nums.length;
        int index = 0;
        while(index < len) {
            if(nums[index] == index || nums[index] == len) {
                index ++;
            } else {
                swap(nums, index, nums[index]);
            }
        }
        // 再次遍历，求缺失
        for(int i = 0; i < len; i ++) {
            if(nums[i] != i) {
                return i;
            }
        }
        return len;
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

---

输出 1

---

解法 2 - 位运算

class Solution {
    public int missingNumber(int[] nums) {
        // 思路：
        // [0, n] 中只有一个元素没有出现，那么再加上 [0, n]后，变为 [0, n] 中只有一个数出现过一次
        int len = nums.length;
        int tmp = 0;
        for(int i = 0; i <= len; i ++) {
            tmp ^= i;
        }
        for(int i: nums) {
            tmp ^= i;
        }
        return tmp;
    }
}

---

输出 2

---

解法 3 - 数学

class Solution {
    public int missingNumber(int[] nums) {
        // 思路：
        // [0, n] 所有元素和 == (len + 1) * len / 2
        int len = nums.length;
        int sum = 0;
        for(int i : nums) {
            sum += i;
        }
        return (len + 1) * len / 2 - sum;
    }
}

---

输出 3