首页 > 其他 > 详细

数组中只出现一次的数字

时间:2014-03-20 10:44:11      阅读:493      评论:0      收藏:0      [点我收藏+]

题目:一个整型数组里除了两个数字外,其他的数字都出现了两次,请写一个程序找出只出现一次的数字,要求时间复杂度O(n),空间复杂度O(1)

算法:首先对所有数字取异或,找到结果中有一位不为0的位置,然后,对所有元素分组,分为两个部分;然后对每个部分分别取异或

bubuko.com,布布扣
bubuko.com,布布扣
import java.util.*;

public class Main21 {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n;
        int[] numb;
        while (scanner.hasNext()) {
            n = scanner.nextInt();
            numb = new int[n];
            for (int i = 0; i < n; i++) {
                numb[i] = scanner.nextInt();
            }
            int value = 0;
            for (int i = 0; i < n; i++) {
                value ^= numb[i];
            }
            int index = 0;
            while (((value & 1) == 0) && (index < 32)) {
                value = value >> 1;
                index++;
            }
            int num1 = 0, num2 = 0;
            for (int i = 0; i < n; i++) {
                value = numb[i] >> index;
                if ((value & 1) == 0) {
                    num1 ^= numb[i];
                } else {
                    num2 ^= numb[i];
                }
            }
            System.out.println(num1);
            System.out.println(num2);
        }
    }
}
bubuko.com,布布扣

 

bubuko.com,布布扣

数组中只出现一次的数字,布布扣,bubuko.com

数组中只出现一次的数字

原文:http://www.cnblogs.com/csxf/p/3613001.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!