带薪刷题==摸鱼

LeetCode 137. Single Number II 的一种解法,时间O(n) 空间O(1)


Given an integer array nums where every element appears three times except for one, which appears exactly onceFind the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each element in nums appears exactly three times except for one element which appears once.


思路:

创造一种按位运算,重复一次是其本身,重复三次归零。(类似异或,异或是重复两次归零)

需要引入一个n,用来保存当前已经有两个的这种状态。

列出所有状态如下,n1为当前的n,a1为当前的数字,a2为输入的数字(因为输入是一次,所以不需要n2)。

a3为计算后的数字,n3为计算后的n。



分别考虑a和n的状态转移,可以得到以下公式:

    a3 = ~n1 & (a1 ^ a2);

    n3 = ~n1 & (a1 & a2) | n1 & ~a2;


到这步就可以写代码了:


为了好看,公式可以进一步化简成:

    a3 = ~n1 & (a1 ^ a2);

    n3 = ~a3 & (n1 ^ a2);


注意顺序不能反了,n3依赖了计算后的a3。

写成代码就是:





评论

发表评论