【脑洞大挑战】一道有趣的编程题
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]

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

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

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

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

#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 long now = (unsigned)nums[i] % j + prevresult % j;
			result += (now - prev) % j;
			prev = now;
		}
		prevresult = result;
	}

	printf("%d\n", (int)prevresult);

	return 0;
}

[修改于 3 年前 - 2016-10-19 23:06:07]

折叠评论
加载评论中,请稍候...
折叠评论
3楼
引用 Cirno:
欢迎大家解题,过阵子会谈谈解法
刚才网上看了看解答,确实脑洞大
折叠评论
加载评论中,请稍候...
折叠评论
4楼

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

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

[修改于 3 年前 - 2016-10-19 22:55:34]

折叠评论
加载评论中,请稍候...
折叠评论
2016-10-20 10:13:19
5楼
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;
}

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

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
6楼

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

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

仔细想了想,上述问题本身不就是线性时间的么,只要你用两层循环分别遍历给定整数空间,然后对两个数分别进行线性查找,两个都找到的进行xor最大值统计,找不到的直接忽略即可😒😒😒我觉得这才是最暴力的方法

[修改于 3 年前 - 2016-10-20 20:15:09]

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

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

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

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

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

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
11楼
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
折叠评论
加载评论中,请稍候...
折叠评论
12楼
引用 Cirno:
不是说 O(n) 么?
对啊,线性时间→_→统计一个数列中数有哪些出现了不是线性时间么→_→要是觉得不严谨咱再在第二个双层循环里边的else语句里塞个空语句

[修改于 3 年前 - 2016-10-23 08:55:29]

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
13楼
引用 acmilan:
对啊,线性时间→_→统计一个数列中数有哪些出现了不是线性时间么→_→要是觉得不严谨咱再在第二个双层循环里边的else语句里塞个空语句
你两层循环就是 n(n-1) 次了。。。。
折叠评论
加载评论中,请稍候...
折叠评论
14楼
引用 Cirno:
你两层循环就是 n(n-1) 次了。。。。
231*231啊,怎么会是n(n-1)→_→
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
15楼
引用 acmilan:
231*231啊,怎么会是n(n-1)→_→
→_→。。。。啊,题目里边其实是 2^31,不是 231,编辑错了
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
16楼
引用 acmilan:
231*231啊,怎么会是n(n-1)→_→
但还是理解不能你的思路。。。算了
折叠评论
加载评论中,请稍候...
折叠评论
17楼
引用 Cirno:
→_→。。。。啊,题目里边其实是 2^31,不是 231,编辑错了
那就只能用你的方法了→_→
折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
18楼
引用 acmilan:
那就只能用你的方法了→_→
虽然打错但本质上没区别啊。。。表示完全没有理解你的意思😂
折叠评论
加载评论中,请稍候...
折叠评论
19楼
引用 Cirno:
虽然打错但本质上没区别啊。。。表示完全没有理解你的意思😂
怎么会本质上没区别→_→231和2^31差别还是很大的

[修改于 3 年前 - 2016-10-23 09:54:58]

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
20楼
引用 acmilan:
怎么会本质上没区别→_→231和2^31差别还是很大的
这对算法自由度没有半毛钱影响啊
折叠评论
加载评论中,请稍候...
折叠评论
21楼
引用 Cirno:
这对算法自由度没有半毛钱影响啊
→_→第一不具备可行性(至少要跑147年),第二循环内的隐性时间增长变成上不封顶了

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

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
22楼
引用 acmilan:
→_→第一不具备可行性(至少要跑147年),第二循环内的隐性时间增长变成上不封顶了
彻底服了你。。。。花那么多时间折腾各种冷门编程框架,学一下正经的computer science基础不好么,以亲身经验表示研究“规律”远比“规则”来得长远。此帖作废,不再更新。。不再回复反驳。。这里完全讨论不下去。。。

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

折叠评论
加载评论中,请稍候...
折叠评论
23楼
引用 Cirno:
彻底服了你。。。。花那么多时间折腾各种冷门编程框架,学一下正经的computer science基础不好么,研究“规律”远比“规则”来得长远。此帖作废,不再更新。。这完全讨论不下去。。。
引用 Cirno:
让O(n)来得更凶猛吧
→_→以为自己是这个坛里唯一的大神么,别人只是懒得说你罢了

[修改于 3 年前 - 2016-10-24 00:38:49]

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

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

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{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