网站访问速度优化,广安做网站,互联网推广员,百度电脑版网页版入口题目描述
给定一个包含 0, 1, 2, …, n 中 n 个数的序列#xff0c;找出 0 … n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8解法
思路1#xff1a;使用额外数组存储0~n#xff0c;遍历数组#xff0c;缺失…题目描述
给定一个包含 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 i0;iarr.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 temp0;for(int i0;inums.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 i0;inums.length;i) {if(nums[i]!i) {return i;}}return nums.length;}思路2位运算 利用异或(不同为1相同为0)特性 0^44 4^40 4^ 0 ^40
public int missingNumber(int[] nums) {int res 0;for(int i0;inums.length;i) {res res^i^nums[i];}return res^nums.length;}
