【脑洞大挑战】一道有趣的编程题
Cirno2016/10/19软件综合 IP:美国
今天看到一道算法题:

有一个整数数列,其元素除了一个只出现一次,其余的均出现三次,像这样: [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?
来自:计算机科学 / 软件综合
24
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
Cirno 作者
7年6个月前 修改于 7年6个月前 IP:美国
826905
欢迎大家解题,过阵子会谈谈解法
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 修改于 7年6个月前 IP:四川
826908

感觉三进制不进位加法应该能解决这个问题

用暴力法实现了一下,不知道怎么优化

更新:发现负数处理问题,调试发现直接(unsigned long long)相当于(unsigned long long)(long long),会扩展符号位,要(unsigned long long)(unsigned)才会用零填充高位,坑了。。。已修正

<code class="language-cpp">#include <stdio.h>

int main(int argc, char *argv[])
{
	int count, nums[256];
	scanf("%d", &count);
	for (int i = 0; i < count; i++)
		scanf("%d", &nums[i]);

	unsigned long long prevresult = count > 0 ? (unsigned)nums[0] : 0;
	for (int i = 1; i < count; i++)
	{
		unsigned long long prev = 0, result = 0;
		for (unsigned long long j = 3; j <= 10460353203ull; j *="3)" { unsigned long now="(unsigned)nums[i]" % + prevresult j; result - prev) prev="now;" } printf("%d\n", (int)prevresult); return 0; < code></=></stdio.h></code>
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
celeron533
7年6个月前 IP:上海
826919
引用 Cirno:
欢迎大家解题,过阵子会谈谈解法
刚才网上看了看解答,确实脑洞大
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 修改于 7年6个月前 IP:四川
826925

看了下其它人的解答,有的确实是用三进制不进位加法的方法,有的不是实现真实的三进制不进位加法,而是用按位计数的方法实现的。。。

要是2个的话就简单了,直接一路xor出结果。。。

引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
cs_net
7年6个月前 修改于 7年6个月前 IP:四川
826943
public int GetNumber(int[] nums)
{
      int ones = 0,twos=0;
      for(int i=0;i<nums.Length;i++)
      {
            ones = (ones ^ nums[i]) & ~twos;
            twos = (twos ^ nums[i]) & ~ones;
      }
      return ones;
}
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 修改于 7年6个月前 IP:美国
826954

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

<code>Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.
</code>
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 修改于 7年6个月前 IP:四川
826963
上述题目可以经过线性时间的变换,转换为常数时间问题(因为相同数值的xor等于0,又限制了数值范围),所以。。。又回到了暴力法😂😂😂

仔细想了想,上述问题本身不就是线性时间的么,只要你用两层循环分别遍历给定整数空间,然后对两个数分别进行线性查找,两个都找到的进行xor最大值统计,找不到的直接忽略即可😒😒😒我觉得这才是最暴力的方法
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 修改于 7年6个月前 IP:美国
826977
引用 acmilan:
上述题目可以经过线性时间的变换,转换为常数时间问题(因为相同数值的xor等于0,又限制了数值范围),所以。。。又回到了暴力法😂😂😂

仔细想了想,上述问题本身不就是线性时间的么,只要你用两层循环……
我是用 Binary Trie 做的,先用O(31n)时间建Trie,然后再用同样时间把每个数从 Trie 里边过一遍,但是遇到有分岔的时候就走岔道,并且update这个 bit,过完一遍就得到 一个新的 xor 值。其他的解法还在想
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 IP:四川
826990
先统计231个整数中有哪些出现了,然后两层循环分别遍历这231个整数,找到最大的xor值。。。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 修改于 7年6个月前 IP:美国
827061
引用 acmilan:
先统计231个整数中有哪些出现了,然后两层循环分别遍历这231个整数,找到最大的xor值。。。
不是说 O(n) 么?
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 IP:美国
827062
<code class="language-Python">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)))></code>
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 修改于 7年6个月前 IP:四川
827065
引用 Cirno:
不是说 O(n) 么?
对啊,线性时间→_→统计一个数列中数有哪些出现了不是线性时间么→_→要是觉得不严谨咱再在第二个双层循环里边的else语句里塞个空语句
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 IP:美国
827067
引用 acmilan:
对啊,线性时间→_→统计一个数列中数有哪些出现了不是线性时间么→_→要是觉得不严谨咱再在第二个双层循环里边的else语句里塞个空语句
你两层循环就是 n(n-1) 次了。。。。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 IP:四川
827068
引用 Cirno:
你两层循环就是 n(n-1) 次了。。。。
231*231啊,怎么会是n(n-1)→_→
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 IP:美国
827070
引用 acmilan:
231*231啊,怎么会是n(n-1)→_→
→_→。。。。啊,题目里边其实是 2^31,不是 231,编辑错了
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 IP:美国
827072
引用 acmilan:
231*231啊,怎么会是n(n-1)→_→
但还是理解不能你的思路。。。算了
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 IP:四川
827074
引用 Cirno:
→_→。。。。啊,题目里边其实是 2^31,不是 231,编辑错了
那就只能用你的方法了→_→
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 IP:美国
827075
引用 acmilan:
那就只能用你的方法了→_→
虽然打错但本质上没区别啊。。。表示完全没有理解你的意思😂
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 修改于 7年6个月前 IP:四川
827076
引用 Cirno:
虽然打错但本质上没区别啊。。。表示完全没有理解你的意思😂
怎么会本质上没区别→_→231和2^31差别还是很大的
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 IP:美国
827077
引用 acmilan:
怎么会本质上没区别→_→231和2^31差别还是很大的
这对算法自由度没有半毛钱影响啊
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 修改于 7年6个月前 IP:四川
827078
引用 Cirno:
这对算法自由度没有半毛钱影响啊
→_→第一不具备可行性(至少要跑147年),第二循环内的隐性时间增长变成上不封顶了
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
Cirno作者
7年6个月前 修改于 7年6个月前 IP:美国
827079
引用 acmilan:
→_→第一不具备可行性(至少要跑147年),第二循环内的隐性时间增长变成上不封顶了
彻底服了你。。。。花那么多时间折腾各种冷门编程框架,学一下正经的computer science基础不好么,以亲身经验表示研究“规律”远比“规则”来得长远。此帖作废,不再更新。。不再回复反驳。。这里完全讨论不下去。。。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
acmilan
7年6个月前 修改于 7年6个月前 IP:四川
827080
引用 Cirno:
彻底服了你。。。。花那么多时间折腾各种冷门编程框架,学一下正经的computer science基础不好么,研究“规律”远比“规则”来得长远。此帖作废,不再更新。。这完全讨论不下去。。。
引用 Cirno:
让O(n)来得更凶猛吧
→_→以为自己是这个坛里唯一的大神么,别人只是懒得说你罢了
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

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

所属专业
上级专业
同级专业
Cirno
专家 进士 老干部 学者 机友 笔友
文章
34
回复
359
学术分
2
2012/09/03注册,9天15时前活动

Machine Learning, computer vision enthusiast

Google

主体类型:个人
所属领域:无
认证方式:手机号
IP归属地:未同步
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}