64、缺失数字

题目描述

一开始撸出来的代码

class Solution {
    public int missingNumber(int[] nums) {
       Arrays.sort(nums);
        
       /// System.out.println(nums.toString());
        int i;
        for ( i = 0; i < nums.length-1; i++) {
			int j = nums[i];
			if(nums[i] + 1 != nums[i+1]){
				break;
			}
			
		}
          if(nums[0] == 1){
        	return 0;
        }
        return nums[i] + 1;  
    }
}

后续改进的代码，直接使用两个for循环，需要注意的是：第一个for循环是将s这个布尔数组进行初始化，因为默认是false，第二个for循环是找出s这个数组中的为false的下标，那么就返回这个下标

class Solution {
    public int missingNumber(int[] nums) {
        boolean s[] = new boolean[nums.length+1];
		for (int i = 0; i < nums.length; i++) {
			s[nums[i]] = true;
		}
		for (int i = 0; i < nums.length+1; i++) {
			boolean b = s[i];
			if(!b){
				return i;
			}
		}
		
		return 0;
    }
}

排名靠前的代码
好嘛，全部揉在一起了

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int i :nums)
            sum+=i;
        return (((int)Math.pow(n,2)+n)-2*sum)/2;
    }
}

这个代码直接进行异或
还是有点道理的，比如：只有0和2那么异或就是1，返回1即可，但是还要和0，1，2进行异或，这样才能找到，所以最后的是0-n（包括n）

class Solution {
    public int missingNumber(int[] nums) {
        //先求出n
		int n = nums.length;
		
		//将所给的序列的所有数以及[0,n]相互异或，余下的数就是只出现了一次的数
		//即没有出现在序列中的数
		int count = 0;
		for(int i=0;i<nums.length;i++){
			count ^= nums[i];
		}
		
		for(int i=0;i<=n;i++){
			count ^= i;
		}
		return count;
    }
}