要求:
给定一个整型数组,其中除了一个元素之外,每个元素都出现三次。找出这个元素
注意:算法的时间复杂度应为O(n),最好不使用额外的内存空间
难度:中等
分析:
与#136类似,都是考察位运算。不过出现两次的可以使用异或运算的特性 n XOR n = 0, n XOR 0 = n,即某一位上出现偶数次1将该位置为0,出现奇数次1将该位置为1,这样扫一遍数组即可得到结果。
类似的,对于本题出现三次的情况,我们需要构造一个与异或类似的运算,使某一位出现三次1时置为0,出现3n+1次1时置为1。取三个整型值ones, twos, threes,均初始化为0,分别用于记录某一位出现1的次数。为简单起见,设输入数组M = {1,1, ... 1}, M中元素个数为m,则对于每一个输入项M[i],令:
twos = twos | ones & M[i]
ones = ones ^ M[i]
threes = ones & threes
ones = ones & ~threes // 当threes为1时将ones和twos置为0
twos = twos & ~threes
故m=3n时,threes = 1, m=3n+1时,ones = 1。
解决方案:
Java - 248ms
public int singleNumber(int[] A) { if(A.length==0) { return 0; } int ones=0, twos=0, threes=0; for (int i=0;i<A.length;i++){ twos |= ones & A[i]; ones = ones ^ A[i]; threes = ones & twos; ones = ones & ~threes; twos = twos & ~threes; } return ones; }
相关推荐
面试题 02.06. 回文链表标签:栈、递归、链表、双指针难度:简单题目大意给定一个链表的头节点 head。然后再使用两个指针,一个指向数组开始位置,一个指向数
2. 位运算将出现三次的元素换成二进制形式放在一起,其二进制对应位置上,出现 1 的个数一定是 3 的倍数(包括 0)。此时,如果在放进来只出现一次的元素,则某
如果在当前组合中增加一个 (,则 symbol += 1,如果增加一个 ),则 symbol -= 1。如果最终生成 2 * n 的括号组合,并且 symbol
解题思路如果 n ,则 n 必然不是丑数,直接返回 False。对 n 分别进行 2、3、5 的整除操作,直到 n 被除完,如果 n 最终为 1,则 n
要求:对于 0 ≤ i ≤ n 的每一个 i,计算其二进制表示中 1 的个数,返回一个长度为 n + 1 的数组 ans 作为答案。解题思路可以根据整数的二进制
2. 位运算将出现三次的元素换成二进制形式放在一起,其二进制对应位置上,出现 1 的个数一定是 3 的倍数(包括 0)。此时,如果在放进来只出现一次的元素,则某
解题思路序列化:通过深度优先搜索的方式,递归遍历节点,以 root.val、len(root.children)、root.children 的顺序生成序列化结
970. 强整数对数运算function powerfulIntegers(x: number, y: number, bound: number): numb
然后通过用循环来解:假设第一个for循环是一个数组的循环,而后它的内嵌循环是也是这个数组,只是下标从0变成了1,这样,在第一次循环时,第1个元素会与其他所有元素
示例 1:输入: a = "11", b = "10"输出: "101"示例 2:输入: a = "1010", b = "1011"输出: "10101"提示
给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
0090. 子集 II标签:位运算、数组、回溯难度:中等题目大意给定一个整数数组 nums,其中可能包含重复元素。回溯的时候,每次遍历从当前位置的下一个位置进行
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode思维导图-位运算
解题思路如果最后剩下1-3个石头,你肯定是赢家,如果此时剩下4个石头,你无论拿多少个,对方一定会赢。如果此时剩下5个石头,这时你的最佳策略是拿走一个石头,这是对
令 dp(i, j) 为亚历克斯可以获得的最大分数,其中剩下的堆中的石子数是 piles[i], piles[i+1], ..., piles[j]。我们可以根
示例1输入:[[1,0,1],[0,0,0],[1,0,1]]输出:2解释:海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。解题思路
示例1输出:"1[.]1[.]1[.]1"示例2输出:"255[.]100[.]50[.]0"代码实现本文链接:
要考虑第一个节点要被删除的情况代码实现self.next = Nonedef removeElements(self, head: ListNode, val: