缺失数字

超、凢脫俗 2022-02-25 11:52 189阅读 0赞

**题目描述**

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

**示例 1:**

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

**示例 2:**

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

**解法**

思路1：使用额外数组存储0~n，遍历数组，缺失的即为答案

/**
     * 使用额外数组
     * 空间复杂度O(n)
     * 时间复杂度O(n)
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
            int []arr = new int[nums.length +1];
            for(int num:nums) {
            	arr[num] = num;
            }
            for(int i=0;i<arr.length;i++) {
            	if(arr[i] == 0) {
            		return i;
            	}
            }
            return 0;
        }

思路2：原数组排序，对空间进行优化

/**
    	 * 思路2：数组排序
    	 * 找到缺失的那个数字
    	 * 空间复杂度O(n)
    	 * 时间复杂度O(1)
    	 * @param nums
    	 * @return
    	 */
    	public int missingNumber(int[] nums) {
            int temp=0;
    		for(int i=0;i<nums.length;i++) {
            	if(nums[i] != i && nums[i] != nums.length) {
            		temp = nums[nums[i]];
            		nums[nums[i]] = nums[i];
            		nums[i] = temp;
            		i--;
            	}
            }
    		for(int i=0;i<nums.length;i++) {
    			if(nums[i]!=i) {
    				return i;
    			}
    		}
    		return nums.length;
        }

思路2：位运算  
利用**异或**(不同为1，相同为0)特性：  
0^4=4  
4^4=0  
4^ 0 ^4=0

public int missingNumber(int[] nums) {
    		int res = 0;
    		for(int i=0;i<nums.length;i++) {
    			res = res^i^nums[i];
    		}
    		return res^nums.length;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode268. 缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。示例 1: 输入: \[3,0,1\] 输出: 2

港控/mmm°/ 2023年07月03日 04:50/ 0 赞/ 6 阅读

相关 LeetCode:268. Missing Number缺失数字(C语言)

题目描述：给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。示例 1: 输入: \[3,0,1\] 输

痛定思痛。/ 2022年12月03日 02:28/ 0 赞/ 152 阅读

相关 268. 缺失数字（JS实现）

1 题目 > 给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。 > 示例 1: > 输入: \[3,0

柔情只为你懂/ 2022年11月27日 15:50/ 0 赞/ 187 阅读

相关缺失数字（C++牛客网）

class Solution { public: / 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即

谁借莪１个温暖的怀抱￠/ 2022年11月18日 02:26/ 0 赞/ 171 阅读

相关 LeetCode268. 缺失数字

给定一个包含 `0, 1, 2, ..., n` 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。示例 1: 输入: [3,0,1]

雨点打透心脏的1/2处/ 2022年05月23日 03:49/ 0 赞/ 166 阅读

相关 jekyll-paginate 缺失

从 Jekyll 3.0 开始，jekyll-paginate 被移除了，因为与其他核心功能不能很好的协作。如果出现这种提示： > $ jekyll serve > Co

水深无声/ 2022年04月11日 04:54/ 0 赞/ 215 阅读

相关 268. 缺失数字

public class Solution \{ public int missingNumber(int\[\] nums) \{ int missing = num

妖狐艹你老母/ 2022年04月01日 03:28/ 0 赞/ 199 阅读

相关 LeetCode——缺失数字

题目：给定一个包含 `0, 1, 2, ..., n` 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。示例 1: 输入: [3,0,1]

绝地灬酷狼/ 2022年03月27日 13:51/ 0 赞/ 316 阅读

相关 LeetCode268——缺失数字

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

青旅半醒/ 2022年03月12日 11:14/ 0 赞/ 183 阅读

相关缺失数字

题目描述给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。示例 1: 输入: [3,0,1]

超、凢脫俗/ 2022年02月25日 11:52/ 0 赞/ 190 阅读