leetcode 268. Missing Number

迷南。 2023-07-12 05:05 1阅读 0赞

**目录**

一、问题分析

二、代码实现

1、数学运算

2、位运算

--------------------

[https://leetcode.com/problems/missing-number/][https_leetcode.com_problems_missing-number]

给定一个数组包含n个独一无二的元素，元素大小在\[0, n\]之间，求出数组中所缺失的那个整数，要求时间O(n)，空间O(1)

## 一、问题分析 ##

测试用例：

Example 1:
    Input: [3,0,1]
    Output: 2
    
    Example 2:
    Input: [9,6,4,2,3,5,7,0,1]
    Output: 8

## 二、代码实现 ##

### 1、数学运算 ###

class Solution {
        
        //避免溢出
        public int missingNumber2(int[] nums) {
            int ret = nums.length;  //n
            
            for (int i=0; i<nums.length; i++) {
                ret += i - nums[i]; //ret始终小于等于初始值（n）
            }
            
            return ret;
        }
        
        //可能溢出
        public int missingNumber1(int[] nums) {
            int n = nums.length;
            int ret = n * (n + 1) / 2;  //可能溢出
            for (int i=0; i<n; i++) {
                ret -= nums[i]; //如果上面那句没有溢出，那这里由于不断减小，不可能溢出
            }
            
            return ret;
        }
    }

### 2、位运算 ###

class Solution {
        
        //位运算（避免溢出）
        public int missingNumber3(int[] nums) {
            int ret = nums.length;  //n
            
            for (int i=0; i<nums.length; i++) {
                ret ^= i ^ nums[i];
            }
            
            return ret;
        }
        
    }

参考：

[https://leetcode.com/problems/missing-number/discuss/69832/1%2B-lines-Ruby-Python-Java-C%2B%2B][https_leetcode.com_problems_missing-number_discuss_69832_1_2B-lines-Ruby-Python-Java-C_2B_2B]

[https://leetcode.com/problems/missing-number/discuss/69786/3-different-ideas%3A-XOR-SUM-Binary-Search.-Java-code][https_leetcode.com_problems_missing-number_discuss_69786_3-different-ideas_3A-XOR-SUM-Binary-Search.-Java-code]

[https://leetcode.com/problems/missing-number/discuss/69961/Share-four-different-solutions][https_leetcode.com_problems_missing-number_discuss_69961_Share-four-different-solutions]

[https://leetcode.com/problems/missing-number/discuss/70030/Using-BitSet-Java][https_leetcode.com_problems_missing-number_discuss_70030_Using-BitSet-Java]

[https://leetcode.com/problems/missing-number/discuss/69791/4-Line-Simple-Java-Bit-Manipulate-Solution-with-Explaination][https_leetcode.com_problems_missing-number_discuss_69791_4-Line-Simple-Java-Bit-Manipulate-Solution-with-Explaination]

[https://leetcode.com/problems/missing-number/discuss/70058/Swapping-numbers-to-the-same-index-cell][https_leetcode.com_problems_missing-number_discuss_70058_Swapping-numbers-to-the-same-index-cell]

[https://leetcode.com/problems/missing-number/discuss/69795/Java-solution-O(1)-space-and-O(n)-in-time][https_leetcode.com_problems_missing-number_discuss_69795_Java-solution-O_1_-space-and-O_n_-in-time]

[https://leetcode.com/problems/missing-number/discuss/70093/O(n)-time-O(1)-space-solution.-Use-long-to-cover-corner-cases-if-enough-memory-for-large-input][https_leetcode.com_problems_missing-number_discuss_70093_O_n_-time-O_1_-space-solution.-Use-long-to-cover-corner-cases-if-enough-memory-for-large-input]

[https_leetcode.com_problems_missing-number]: https://leetcode.com/problems/missing-number/
[https_leetcode.com_problems_missing-number_discuss_69832_1_2B-lines-Ruby-Python-Java-C_2B_2B]: https://leetcode.com/problems/missing-number/discuss/69832/1%2B-lines-Ruby-Python-Java-C%2B%2B
[https_leetcode.com_problems_missing-number_discuss_69786_3-different-ideas_3A-XOR-SUM-Binary-Search.-Java-code]: https://leetcode.com/problems/missing-number/discuss/69786/3-different-ideas%3A-XOR-SUM-Binary-Search.-Java-code
[https_leetcode.com_problems_missing-number_discuss_69961_Share-four-different-solutions]: https://leetcode.com/problems/missing-number/discuss/69961/Share-four-different-solutions
[https_leetcode.com_problems_missing-number_discuss_70030_Using-BitSet-Java]: https://leetcode.com/problems/missing-number/discuss/70030/Using-BitSet-Java
[https_leetcode.com_problems_missing-number_discuss_69791_4-Line-Simple-Java-Bit-Manipulate-Solution-with-Explaination]: https://leetcode.com/problems/missing-number/discuss/69791/4-Line-Simple-Java-Bit-Manipulate-Solution-with-Explaination
[https_leetcode.com_problems_missing-number_discuss_70058_Swapping-numbers-to-the-same-index-cell]: https://leetcode.com/problems/missing-number/discuss/70058/Swapping-numbers-to-the-same-index-cell
[https_leetcode.com_problems_missing-number_discuss_69795_Java-solution-O_1_-space-and-O_n_-in-time]: https://leetcode.com/problems/missing-number/discuss/69795/Java-solution-O%281%29-space-and-O%28n%29-in-time
[https_leetcode.com_problems_missing-number_discuss_70093_O_n_-time-O_1_-space-solution.-Use-long-to-cover-corner-cases-if-enough-memory-for-large-input]: https://leetcode.com/problems/missing-number/discuss/70093/O%28n%29-time-O%281%29-space-solution.-Use-long-to-cover-corner-cases-if-enough-memory-for-large-input