268. Missing Number

r囧r小猫 2022-05-26 22:58 310阅读 0赞

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

  1. /** * Created by Joe on 2018/4/7. * 268. Missing Number * https://leetcode.com/problems/missing-number/description/ */
  2. public class P268 { 
  3.     public int missingNumber(int[] nums) {
  4.         int sum = 0;
  5.         for(int num: nums)
  6.             sum += num;
  8.         return (nums.length * (nums.length + 1) )/ 2 - sum;
  9.     }
  10. }

因为假定的是一个连续的序列找缺失数字，所以相当于等差数列求和再减去所给的所有数就是所得。

但是这个方法还是比较笨重，而且有数据溢出的风险，评论区有一个位操作的方法很好。

  1. public int missingNumber(int[] nums) {
  3.     int xor = 0, i = 0;
  4.     for (i = 0; i < nums.length; i++) {
  5.         xor = xor ^ i ^ nums[i];
  6.     }
  8.     return xor ^ i;
  9. }

其主要思路是异或操作，异或操作a^b^b =a，如果有两个相同的数字进行了^操作，这个数字就会被抵消。

发表评论

表情：
评论列表 （有 0 条评论，310人围观）

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

相关阅读