欢迎大家解题，过阵子会谈谈解法
引用
评论
【脑洞大挑战】一道有趣的编程题
今天看到一道算法题：
有一个整数数列，其元素除了一个只出现一次，其余的均出现三次，像这样: [2,2,2,1,3,4,4,3,4,3]。
要求设计一个 O(n) 算法，找出这个只出现一次的整数。
原题：
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
有一个整数数列，其元素除了一个只出现一次，其余的均出现三次，像这样: [2,2,2,1,3,4,4,3,4,3]。
要求设计一个 O(n) 算法，找出这个只出现一次的整数。
原题：
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
让O(n)来得更凶猛吧
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 2^31.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.
引用
评论
引用 acmilan:我是用 Binary Trie 做的，先用O(31n)时间建Trie，然后再用同样时间把每个数从 Trie 里边过一遍，但是遇到有分岔的时候就走岔道，并且update这个 bit，过完一遍就得到 一个新的 xor 值。其他的解法还在想
上述题目可以经过线性时间的变换，转换为常数时间问题（因为相同数值的xor等于0，又限制了数值范围），所以。。。又回到了暴力法
仔细想了想，上述问题本身不就是线性时间的么，只要你用两层循环……
引用
评论
引用 acmilan:不是说 O(n) 么？
先统计231个整数中有哪些出现了，然后两层循环分别遍历这231个整数，找到最大的xor值。。。
引用
评论
class Solution(object):
def findMaximumXOR(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
head=(None,None)
for num in nums:
node=head
for bit in range(32)[::-1]:
chd=int(bool(num&(1<<bit))) if node[chd]="=None:" newnode="(None,None)" node="NewNode" else: maxxor="0" for num in nums: curxor="0" bit range(32)[::-1]: chd="int(bool(num&(1<<bit)))" node[1^chd]: curxor|="1<<bit" return < code></bit)))>引用
评论
引用 acmilan:你两层循环就是 n(n-1) 次了。。。。
对啊，线性时间→_→统计一个数列中数有哪些出现了不是线性时间么→_→要是觉得不严谨咱再在第二个双层循环里边的else语句里塞个空语句
引用
评论
引用 acmilan:→_→。。。。啊，题目里边其实是 2^31，不是 231，编辑错了
231*231啊，怎么会是n(n-1)→_→
引用
评论