汉明距离、位 1 的个数、缺失数字

汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目

给出两个整数 x 和 y，计算它们之间的汉明距离

注意： 0 ≤ x, y < 231

示例

输入: x = 1, y = 4
​
输出: 2
​
解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置

方法一

思路

题目要求比较二进制不同位，那我们就转化为二进制，再做比较

详解

1. 将两个数字转换为二进制字符串

2. 比较字符串长度，短的数组在前面补 0

3. 最后比较这两个数组的相同索引，不相同则 +1

代码

const hammingDistance = function (x, y) {
  let xStr = Number(x).toString(2);
  let yStr = Number(y).toString(2);
  const xLen = xStr.length;
  const yLen = yStr.length;
  let counter = 0;
​
  if (xLen > yLen) {
    yStr = Array(xLen - yLen + 1).join('0') + yStr;
  } else if (xLen < yLen) {
    xStr = Array(yLen - xLen + 1).join('0') + xStr;
  }
​
  for (let i = 0; i < xStr.length; i++) {
    if (xStr[i] !== yStr[i]) {
      counter += 1;
    }
  }
  return counter;
};

复杂度分析

• 时间复杂度: $O(n)$​

  与数字转为二进制的长度线性相关，复杂度为 $O(n)$​

• 空间复杂度：$O(n)$​

  与数字转为二进制的长度线性相关，复杂度为 $O(n)$​

方法二 异或

思路

求汉明距离，即求两数不同位的数量。那么将两数做异或运算，即可得到两数不同位的位置

异或^运算法则：两位不同，结果为1，否则为 0

代码

const hammingDistance = function (x, y) {
  return ((x ^ y).toString(2).match(/[1]/g) || []).length;
};

复杂度分析

• 时间复杂度：$O(1)$​

  时间复杂度为常量

• 空间复杂度：$O(1)$​

  复杂度为常量，为 $O(1)$​

方法三 异或

思路

异或取值，转为 string 后用正则匹配 1 的个数

详解

1. 先将两个数异或运算得到z，那么 z 里面 1 的个数就是结果

2. 如果 z 不为 0，那么 z 至少有一位是 1

3. 将 z - 1，会出现两种情况，最右边的 1 就会变为 0 或者 1 后面的所有的 0 都会变成 1，并且 1 变成 0，其余的位不受影响

   比如 101 --> 100 101 & 100 -> 100 100 && 011

4. 右边这部分的 & 运算结果就为 0，然后循环

与&运算法则：两位同时为 1，结果才为 1，否则为 0

const hammingDistance = function (x, y) {
  let z = x ^ y;
  let counter = 0;
​
  while (z) {
    z = z & (z - 1);
    counter++;
  }
  return counter;
};

复杂度分析

• 时间复杂度：$O(n)$​

  与数字转为二进制的长度线性相关，复杂度为 $O(n)$​

• 空间复杂度：$O(1)$​

  复杂度为常量，为 $O(1)$​

位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：128
输出：1
解释：输入整数128的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：-3
输出：1
解释：输入-3的二进制串11111111111111111111111111111101 中，共有31位为 '1'。

方法一 替换法

思路

数字可能有各种形式的，正数、负数、二进制数等等，那么我们可以按照如下步骤，来完成位1个数的统计。 1.把各种数字转成二进制，并且转化为字符串； 2.然后我们可以使用字符串的方法 replace函数 把二进制中的0用空字符串""来代替; 3.最后我们可以计算返回剩余的字符串的长度就是需要统计的位1的个数。

详解

1. 对于给定的目标数转换为二进制数并赋值给一个新的常量 seconds;

2. 设置一个新的变量 one 并赋值为 seconds 去除非 1 的 新字符串;

3. 返回上述常量 one 的长度即为所求的位 1 的个数。

代码

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
const hammingWeight = function (n) {
  // 对于任一数字n处理为2进制的字符串
  const seconds = n.toString('2');
  // 删除字符串中的“0”
  const one = seconds.replace(/0/g, '');
  return one.length;
};

复杂度分析

• 时间复杂度：$O(1)$​

  对于每个元素，通过把目标元素用空格替换来获取，这将耗费 $O(1)$ 的时间。

• 空间复杂度：$O(1)$​

  上述解法中只申请了一个变量空间，没有申请额外的空间，因此复杂度为 $O(1)$。

方法二 位操作技巧法

思路

解题思路： 这里关键的想法是对于任意数字 n ，我们需要把二进制的每一位 1 转换 为 0 。那么，一个整数的二进制中有多少个 1 ，转化操作多少次，即位 1 的个数就是转化的次数。如何把二进制的每一位都转换为 0 呢？ 我们可以考虑用 n 和 n−1 的二进制来理解。在二进制表示中，数字 n 中最低位的 1 总是对应 n−1 中的 0 。因此，将 n 和 n−1 与运算总是能把 n 中最低位的 1 变成 0 ，并保持其他位不变。为了更形象，我们可以用以下图示：

详解

1. 设置一个变量 count ,用来记录 1 的个数；

2. 对任意不为 0 的数字 n 进行循环, 执行二进制的位操作方法，将数字 n 的每一位逐渐转换 为 0；

3. 当每执行一次循环（也就是每转换一位 1 为 0 ）， 变量 count 就执行一次加 1 的操作；

4. 当数字 n 的每一位都为 0 的时候, 循环就结束了；

5. 此时 count 的值也就是我们所求的位1的个数。

代码

const hammingWeight = function (n) {
  let count = 0;
  while (n !== 0) {
    count++;
    n = n & (n - 1);
  }
  return count;
};

复杂度分析

• 时间复杂度：$O(1)$​

  上述解法中，运行时间依赖于数字 n 中 1 的位数。由于这题中 n 是一个 32 位数，所以运行时间复杂度是 $O(1)$ ，n 在最坏情况下 32 。

• 空间复杂度：$O(1)$​

  该表最多需要存储 1 个元素,没有申请额外的空间，所以空间复杂度为 $O(1)$。

缺失数字

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

示例 1：

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

示例 2：

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

方法一 暴力法

思路

暴力法很简单，排序数组，遍历每个元素 x，判断 index 和当前元素是否相等，不相等的时候返回 index，对应的 index 就是缺失的数

详解

1. 对原数组进行从小到大排序

2. 再对 Array 做处理，只有下标和当前值相同的时候，说明这个数值没有缺失

3. 用 reduce 方法返回仅缺失的哪个数字

/**
 * @param {number[]} nums
 * @return {number}
 */
const missingNumber = function (nums) {
  // 对数组进行排序
  return nums.sort((a, b) => a - b).reduce((arr, item, index) => {
    // 判断当index和当前遍历到的值相同的时候，不对arr插入值
    if (item !== index) {
      // 只有不同的时候，才会往arr中塞值
      arr.push(index);
    }
    return arr;
    // 只会有一个数字，所以只取第一个数字
  }, [])[0];
};

复杂度分析

• 时间复杂度： $O(n * logn)$

  对于每个元素，首先通过排序确定数组从小到大的顺序，构造一个从小到大展示的数组，比如 [0,1,3]，再通过查找下标和当前数据不同的值，获取缺失的数字，这将耗费 $O(n * logn)$ 的时间。

• 空间复杂度：$O(1)$​

  遍历的时候，并不会增加新的存储空间，所以空间复杂度是 $O(1)$​

方法二 计算法

思路

计算法通过计算数据缺失的方式得到缺失的数字

详解

1. 对原数组进行所有数据相加

2. 再计算如果不缺失数字的时候，应该得到的相加数字的总和

3. 用第二步计算出的数据减去第一步的数据就是缺失的数字

/**
 * @param {number[]} nums
 * @return {number}
 */
const missingNumber = function (nums) {
  let sum = 0;
  // 计算数组的相加的和
  nums.forEach((i) => { sum += i; });
  const length = nums.length;
  // 计算如果不缺失数字的时候，相加得到的值应该是多少
  const termial = (1 + length) * length / 2;
  // 相减得到缺失的值
  return termial - sum;
};

复杂度分析

• 时间复杂度：$O(n)$​

  会有 2 次遍历数组，所以最终的时间复杂度是 $O(n)$​

• 空间复杂度：$O(1)$​

  会有 2 个临时变量，不会随着入参数组的增加而增加，所以空间复杂度是 $O(1)$​

方法三 按位异或（XOR）法

思路

可以先看看官方对异或的解释：“对于每一个比特位，当两个操作数相应的比特位有且只有一个 1 时，结果为 1，否则为 0。”，既然只缺失一位数字，那么当前元素和当前下标 index 进行异或运算的时候，不缺失的数字响应的比特为一定是不止一个 1，所以可以用此方法算出对应缺失的值

详解

1. 对数组进行遍历

2. 对当前元素和当前下标做异或运算

3. 对上一步计算出的数据进行异或运算

4. 当遍历完成之后，得到的数值就是缺失的数字

/**
 * @param {number[]} nums
 * @return {number}
 */
const missingNumber = function (nums) {
  let res;
  nums.forEach((i, index) => {
    // 异或操作
    res ^= i ^ (index + 1);
  });
  return res;
};

复杂度分析

• 时间复杂度：$O(n)$​

• 空间复杂度：$O(1)$​