leetcode268-确实数字

秒速五厘米 2023-06-15 12:29 5阅读 0赞

### 文章目录 ###

*  缺失数字
 *   *  题目描述
     *  code
     *   *  方式一：
         *   *  执行结果
         *  方式二

# 缺失数字 #

## 题目描述 ##

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
    输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
    输出: 8

## code ##

### 方式一： ###

public class Leetcode268 {
    
        @Test
        public  void test(){
            int[] nums = new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1};
    
            Solution solution = new Solution();
            System.out.println(solution.missingNumber(nums));
        }
    
        //找出蓄力中没有出现的数字
        class Solution {
            public int missingNumber(int[] nums) {
                Arrays.sort(nums);
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i] != i) {
                        return i;
                    }
                }
                return nums[nums.length-1]+1;
            }
        }
    }

#### 执行结果 ####

> 9ms, 击败25.36%, 需要进行优化

时间复杂度

> O(n\*log n)

### 方式二 ###

> 因为方式一中，使用了排序，所以消耗了大量的性能开销，需要进行优化,

> 使用异或的方式进行处理

class Solution {
            public int missingNumber(int[] nums) {
                //使用异或进行处理 4^4
                /**
                 *  100
                 *  100
                 *  异或
                 *  ----
                 *  000
                 */
                int res = nums.length;
                for (int i = 0; i < nums.length; ++i){
                    res ^= nums[i];
                    res ^= i;
                }
                return res;
            }
        }