文档章节

【九度OJ1351】|【剑指offer40】数组中只出现一次的数字

aqia358
 aqia358
发布于 2013/10/17 13:28
字数 707
阅读 55
收藏 0
题目描述:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
输入:
每个测试案例包括两行:
第一行包含一个整数n,表示数组大 小。2<=n <= 10^6。
第二行包含n个整数,表示数组元素,元素均为int。
输出:

对应每个测试案例,输出数组中只出现一次的两个数。输出的数字从小到大的顺序。

知识点:异或运算的性质:任何一个数字异或它自己都等于0

    这道题利用异或的几个性质:任何数与其本身异或值都为0,异或运算满足交换律。因此将一组数依次异或,若里面只有一个只出现一次的数,其他的数都出现两次,则最后的结果必然是那个只出现一次的数。
    有了这个解决方法我们就可以解决两个相异的数,如果能够把原数组分为两个子数组。在每个子数组中,包含一个只出现一次的数字,而其他数字都出现两次。如果能够这样拆分原数组,按照前面的办法就是分别求出这两个只出现一次的数字了。

    我们还是从头到尾依次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次,在异或中全部抵消掉 了。由于这两个数字肯定不一样,那么这个异或结果肯定不为0,也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的 位的位置,记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第N位都为1,而第二个子数组的每个数 字的第N位都为0。(这两个数字不同,意味着为1的那个位是相异的)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {

	public static void find(int[] a,int result) {
		int pos = 1;
		while ((result & pos) == 0) {
			pos <<= 1;
		}
		int num1 = 0;
		int num2 = 0;
		for (int j = 0; j < a.length; j++) {
			if ((a[j] & pos) == 0)
				num1 ^= a[j];
			else
				num2 ^= a[j];
		}
		if (num1 < num2)
			System.out.println(num1 + " " + num2);
		else
			System.out.println(num2 + " " + num1);
	}

	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while (st.nextToken() != st.TT_EOF) {
			int length = (int) st.nval;
			int[] array = new int[length];
			int count = 0;
			int result = 0;
			while (count < length) {
				st.nextToken();
				array[count] = (int)st.nval;
				result ^= array[count++];
			}
			find(array,result);
		}
	}

}


© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
面试 19:输出数组中出现次数超过一半的数字(剑指 Offer 26 题)

面试 19:输出数组中出现次数超过一半的数字(剑指 Offer 26 题) 上一篇推文给大家留下的习题来自于《剑指 Offer》第 29 题:数组中超过一半的数字,不知道各位去思考了么? 面试题:数组中...

nanchen2251
08/02
0
0
那些算频率的算法,现在都怎么样了?

面试 19:输出数组中出现次数超过一半的数字(剑指 Offer 26 题) 上一篇推文给大家留下的习题来自于《剑指 Offer》第 29 题:数组中超过一半的数字,不知道各位去思考了么? 面试题:数组中...

南尘
08/02
0
0
[算法总结] 13 道题搞定 BAT 面试——字符串

本文首发于我的个人博客:尾尾部落 1. KMP 算法 谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把...

繁著
09/05
0
0
[剑指offer] 数组中只出现一次的数字

本文首发于我的个人博客:尾尾部落 题目描述 一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。 解题思路 法一:大家都能想到的HashMap法 ...

繁著
07/26
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
06/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 识别慢性能的宏

Page Profiling 给你了有关页面在载入的时候操作缓慢的邪教,你可以将下面的内容添加到调试(debug)级别: Version 3.1 及其后续版本 设置包名字为 com.atlassian.renderer.v2.components.M...

honeymose
11分钟前
0
0
day93-20180920-英语流利阅读-待学习

时尚之觞:外表光鲜靓丽,其实穷得要命 Lala 2018-09-20 1.今日导读 讲到时尚界,我们脑海里浮现的可能都是模特和设计师光鲜靓丽、从容潇洒的模样。可是,最近在法国出版的一本书却颠覆了我们...

飞鱼说编程
27分钟前
0
0
maven的pom.xml用解决版本问题

maven管理库依赖,有个好处就是连同库的依赖的全部jar文件一起下载,免去手工添加的麻烦,但同时也带来了同一个jar会被下载了不同版本的问题,好在pom的配置里面允许用<exclusion>来排除一些...

JAVA码猿
50分钟前
1
0
20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
今天
2
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
42
11

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部