问题：给定一个包含n个不同数字的数组，从0开始，例如0,1,2,…n。找到数组中缺了那个数字。例如输入nums=[0,1,3]，输出2。 思路：高斯 从0到n的和为sum=(1+n)*n/2。只要计算数组的和与sum的差是多少就可以了。
public int missingNumber(int[] nums) { int n = nums.length; int ssum = (1+n)*n/2; int sum = 0; for(int i=0;i<nums.length;i++){ sum += nums[i]; } return ssum-sum; }收获： 1 据说可以用位运算。我想数数1的个数。思路不通。 根据 a^b^b=a，对同一个数进行两次异或，或留下原来的数。同时对数组的小标、数组中的元素的值进行异或。留下的元素就是丢失的元素。 public int missingNumber(int[] nums) { int xor = nums.length; for(int i=0;i
public int missingNumber(int[] nums) { Arrays.sort(nums); int left = 0; int right = nums.length; while(left<right){ int mid = (left+right)/2; if(nums[mid]>mid) right = mid; else left = mid +1; } return left; }参考资料 1 问题 2 讨论
