【算法面试题】如何尽快找到只出现一次的数字

西夏一品堂 发布于 2015/05/24 22:21
阅读 852
收藏 2
在一个数组中除3个数字只出现1次外,其它数字都出现了2次, 要求尽快找出这3个数字。
加载中
1
sxgkwei
sxgkwei
往hashset里面add,如果返回false,就是重复的。
1
jQer
jQer
哈希表记录就完事了,连o(N)都不到
1
0
Altman
Altman
遍历一次,出现过第二次的数字都删了,留下的就是一次的
Altman
Altman
回复 @柏show : 7块钱的麻辣烫
柏show
柏show
回复 @Altman : 这是不是得请我吃顿饭
Altman
Altman
回复 @柏show : 哇日
柏show
柏show
回复 @Altman : 为了回复雷少特意注册了个号
Altman
Altman
回复 @柏show :膜拜吧
下一页
0
tinyhare
tinyhare
先排序,然后看相邻的是否相同
0
寻梦2012
寻梦2012
采用二分法查找
寻梦2012
寻梦2012
@西夏一品堂 就是归并归并排序
西夏一品堂
西夏一品堂
怎么2分查找
0
安西都护府首席程序员
安西都护府首席程序员
int arr[]={1,2,2,3,34,1,3,34,10,23,4};
		
		int numbers[]=new int[3];
		int index=0;
		int a=0;
		
		for (int i = 0,j; i < arr.length; i++) {
			for (j= 0; j < arr.length; j++) {
				if(i!=j&&arr[j]==arr[i])
					break;
			}
			if(j==arr.length)
				numbers[index++]=arr[i];
		}
		
		for (int i = 0; i < numbers.length; i++) {
			System.out.println(numbers[i]);
		}



0
hippieZhou
hippieZhou
其实我认为是有Dictionary<key,value>的形式也是可以的,最后只保存value值为1的是key就可以啦!
htfy96
htfy96
如果只有1个只出现一次可以: int base=0; for (size_t i=0; i<size; ++i) base ^= a[i]; base 值就是只出现一次的……
0
谢辉被人抢注了
谢辉被人抢注了
 一次遍历,看到一个数就给这个数的出现次数加一,最后看结果中出现次数为一的
0
T
Transy
public class TestNum {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,1,2,3,5,6,7,9,8,7,9};
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            if(set.contains(num)){
                set.remove(num);
            }else{
                set.add(num);
            }
        }
    System.out.println(set);
    }
}
返回顶部
顶部