【脑洞大挑战】一道有趣的编程题
Cirno 2016-10-19软件综合
今天看到一道算法题:

有一个整数数列,其元素除了一个只出现一次,其余的均出现三次,像这样: [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?
来自 软件综合
2016-10-19 11:53:34
Cirno(作者)
1楼
欢迎大家解题,过阵子会谈谈解法

[修改于 3 年前 - 2016-10-19 11:53:57]

折叠评论
加载评论中,请稍候...
折叠评论
2016-10-20 12:57:56
2016-10-20 12:57:56
Cirno(作者)
2楼

让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.

[修改于 3 年前 - 2016-10-23 09:30:06]

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
3楼
引用 acmilan:
上述题目可以经过线性时间的变换,转换为常数时间问题(因为相同数值的xor等于0,又限制了数值范围),所以。。。又回到了暴力法😂😂😂

仔细想了想,上述问题本身不就是线性时间的么,只要你用两层循环……
我是用 Binary Trie 做的,先用O(31n)时间建Trie,然后再用同样时间把每个数从 Trie 里边过一遍,但是遇到有分岔的时候就走岔道,并且update这个 bit,过完一遍就得到 一个新的 xor 值。其他的解法还在想

[修改于 3 年前 - 2016-10-20 22:03:13]

折叠评论
加载评论中,请稍候...
折叠评论
2016-10-23 02:31:52
2016-10-23 02:31:52
Cirno(作者)
4楼
引用 acmilan:
先统计231个整数中有哪些出现了,然后两层循环分别遍历这231个整数,找到最大的xor值。。。
不是说 O(n) 么?

[修改于 3 年前 - 2016-10-23 02:47:29]

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
5楼
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[chd]=NewNode
                    node=NewNode
                else:
                    node=node[chd]
        maxXor=0
        for num in nums:
            node=head
            curXor=0
            for bit in range(32)[::-1]:
                chd=int(bool(num&(1<<bit)))
                if node[1^chd]:
                    curXor|=1<<bit
                    node=node[1^chd]
                else:
                    node=node[chd] 
            maxXor=max(maxXor,curXor)
            
        return maxXor
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
6楼
引用 acmilan:
对啊,线性时间→_→统计一个数列中数有哪些出现了不是线性时间么→_→要是觉得不严谨咱再在第二个双层循环里边的else语句里塞个空语句
你两层循环就是 n(n-1) 次了。。。。
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
7楼
引用 acmilan:
231*231啊,怎么会是n(n-1)→_→
→_→。。。。啊,题目里边其实是 2^31,不是 231,编辑错了
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
8楼
引用 acmilan:
231*231啊,怎么会是n(n-1)→_→
但还是理解不能你的思路。。。算了
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
9楼
引用 acmilan:
那就只能用你的方法了→_→
虽然打错但本质上没区别啊。。。表示完全没有理解你的意思😂
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
10楼
引用 acmilan:
怎么会本质上没区别→_→231和2^31差别还是很大的
这对算法自由度没有半毛钱影响啊
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
11楼
引用 acmilan:
→_→第一不具备可行性(至少要跑147年),第二循环内的隐性时间增长变成上不封顶了
彻底服了你。。。。花那么多时间折腾各种冷门编程框架,学一下正经的computer science基础不好么,以亲身经验表示研究“规律”远比“规则”来得长远。此帖作废,不再更新。。不再回复反驳。。这里完全讨论不下去。。。

[修改于 3 年前 - 2016-10-23 10:37:05]

折叠评论
加载评论中,请稍候...
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
ID:{{user.uid}}
{{user.username}}
{{user.info.certsName}}
{{user.description}}
{{format("YYYY/MM/DD", user.toc)}}注册,{{fromNow(user.tlv)}}活动
{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png