likes
comments
collection
share

夯实算法-数组异或操作

作者站长头像
站长
· 阅读数 10

题目:LeetCode

给你两个整数,n 和 start 。

数组 nums 定义为:nums[i] = start + 2*i(下标从 0 开始)且 n == nums.length 。

请返回 nums 中所有元素按位异或(XOR)后得到的结果。

示例 1:

输入:n = 5, start = 0
输出:8
解释:数组 nums 为 [0, 2, 4, 6, 8],其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
     "^" 为按位异或 XOR 运算符。

示例 2:

输入: n = 4, start = 3
输出: 8
解释: 数组 nums 为 [3, 5, 7, 9],其中 (3 ^ 5 ^ 7 ^ 9) = 8.

示例 3:

输入: n = 1, start = 7
输出: 7

示例 4:

输入: n = 10, start = $5$
输出: 2

提示:

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

解题思路

利用按位异或的性质,可以使用 O(1) 的时间得到结果。

根据按位异或的性质,对于二进制表示中的特定位,如果该位出现奇数个 1 则按位异或的结果是 1,如果该位出现偶数个 1 则按位异或的结果是 0。

由于数组 nums 中的任意两个相邻元素之差都是 2,因此数组 nums 中的所有元素的奇偶性相同。

  • 只有当 n 和 start 都是奇数时,按位异或的结果才是奇数,否则按位异或的结果是偶数。将一个奇数减 11 的效果是将该奇数的二进制表示的最低位 1 变成 0,其余位不变。
  • 如果数组 nums 中的所有元素都是奇数,则数组 nums 中的所有元素按位异或的结果(「数组按位异或结果」)可以通过如下方式计算:将数组 nums 中的所有元素减 1,得到 n 个偶数,计算这 n 个偶数的按位异或结果,记为 x,如果 n 和 start 都是奇数则数组按位异或结果为 x+1,否则数组按位异或结果为 x。

代码实现

public int xorOperation(int n, int start) {
    int odd = n & start & 1;
    start -= start & 1;
    return getPrefixXor(start + 2 * (n - 1)) ^ getPrefixXor(start - 2) + odd;
}

public int getPrefixXor(int num) {
    if (num <= 0) {
        return 0;
    }
    int remainder = num % 8;
    if (remainder == 0) {
        return num;
    } else if (remainder == 2) {
        return 2;
    } else if (remainder == 4) {
        return num + 2;
    } else {
        return 0;
    }
}

复杂度分析

  • 空间复杂度:O(1)O(1)O(1)
  • 时间复杂度:O(1)O(1)O(1)