Medium

题目描述

给你一个整数数组 nums。

返回 nums 中按位异或结果非零的最长子序列的长度。如果不存在这样的子序列，返回 0。

示例 1:

输入: nums = [1,2,3]
输出: 2
解释:
一个最长子序列是 [2, 3]。按位异或计算为 2 XOR 3 = 1，非零。

示例 2:

输入: nums = [2,3,4]
输出: 3
解释:
最长子序列是 [2, 3, 4]。按位异或计算为 2 XOR 3 XOR 4 = 5，非零。

约束条件:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

提示:

  • 如果取整个数组会怎样？
  • 如果整个数组的异或结果是 0，移除一个元素会有帮助吗？
  • 如果所有元素都是 0 怎么办？

解题思路

这道题的关键在于理解异或运算的性质和如何构造最长的非零异或子序列。

核心思路是：

  1. 优先考虑整个数组：首先计算整个数组的异或结果，如果非零，那么答案就是数组长度。
  2. 处理全零情况：如果所有元素都是 0，那么任何子序列的异或都是 0，答案为 0。
  3. 处理异或为零的情况：如果整个数组异或为 0，我们需要移除一个元素来使异或变为非零。此时答案是 n-1。

为什么移除一个元素就能解决问题？设整个数组异或为 S，移除元素 x 后的异或为 S XOR x = 0 XOR x = x。只要 x ≠ 0，结果就非零。

算法步骤：

  1. 计算整个数组的异或值
  2. 如果异或值非零，返回数组长度
  3. 如果异或值为零，检查是否存在非零元素：
    • 如果存在非零元素，返回 n-1
    • 如果所有元素都是零，返回 0

时间复杂度 O(n)，空间复杂度 O(1)，这是最优解法。

代码实现

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        int totalXor = 0;
        
        // 计算整个数组的异或值
        for (int num : nums) {
            totalXor ^= num;
        }
        
        // 如果整个数组异或非零，返回数组长度
        if (totalXor != 0) {
            return n;
        }
        
        // 如果整个数组异或为零，检查是否有非零元素
        for (int num : nums) {
            if (num != 0) {
                return n - 1;  // 移除任意一个非零元素
            }
        }
        
        return 0;  // 所有元素都是零
    }
};

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        n = len(nums)
        total_xor = 0
        
        # 计算整个数组的异或值
        for num in nums:
            total_xor ^= num
        
        # 如果整个数组异或非零，返回数组长度
        if total_xor != 0:
            return n
        
        # 如果整个数组异或为零，检查是否有非零元素
        for num in nums:
            if num != 0:
                return n - 1  # 移除任意一个非零元素
        
        return 0  # 所有元素都是零

public class Solution {
    public int LongestSubsequence(int[] nums) {
        int n = nums.Length;
        int totalXor = 0;
        
        // 计算整个数组的异或值
        foreach (int num in nums) {
            totalXor ^= num;
        }
        
        // 如果整个数组异或非零，返回数组长度
        if (totalXor != 0) {
            return n;
        }
        
        // 如果整个数组异或为零，检查是否有非零元素
        foreach (int num in nums) {
            if (num != 0) {
                return n - 1;  // 移除任意一个非零元素
            }
        }
        
        return 0;  // 所有元素都是零
    }
}

var longestSubsequence = function(nums) {
    const n = nums.length;
    let totalXor = 0;
    
    // 计算整个数组的异或值
    for (const num of nums) {
        totalXor ^= num;
    }
    
    // 如果整个数组异或非零，返回数组长度
    if (totalXor !== 0) {
        return n;
    }
    
    // 如果整个数组异或为零，检查是否有非零元素
    for (const num of nums) {
        if (num !== 0) {
            return n - 1;  // 移除任意一个非零元素
        }
    }
    
    return 0;  // 所有元素都是零
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 为数组长度。算法只需要遍历数组两次，每次都是线性时间，且只使用常数额外空间。