137. 只出现一次的数字 II

137. 只出现一次的数字 II

难度: 中等

来源: 每日一题 2023.10.15

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

class Solution {
    public int maxProfit(int[] prices) {

    }
}

分析与题解

• 位运算

  这个题目一开始做的时候也是没有太好的思路, 看了官方题解, 感觉解法3和解法4有点太偏了. 还是第二种方式比较好理解一点.

  解法2的核心思想是对于最后的结果换算成二级制是有32位( -2^31 <= nums[i] <= 2^31 - 1 ). 那么我们就对每一位进行判断, 如果结果数字在 i 位没有数字, 那么这一位一定能被3整除. 因为只可能是3的倍数. 不能整除,那就是结果在这一数位也是有值的.

  我们一起看一下具体的解题过程.

  class Solution {
      public int singleNumber(int[] nums) {
          int result = 0;
          int tempSum = 0;
          for(int i = 0; i < 32; i++) {
              tempSum = 0;
              for (int num : nums) {
                  tempSum += (num >> i) & 1;
              }
              if (tempSum % 3 != 0) {
                  result |= 1 << i;
              }
          }
          return result;
      }
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(32n) , 虽然是嵌套循环, 但是外部是32位, 固定写死的, 可以认为时间复杂度与 nums长度 成线性关系.
  • 空间复杂度: O(1), 临时数位和tempSum 是常量级别的空间复杂度.

  结果如下所示.