文档章节

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

aqia358
 aqia358
发布于 2013/10/17 13:28
字数 707
阅读 57
收藏 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 题) 上一篇推文给大家留下的习题来自于《剑指 Offer》第 29 题:数组中超过一半的数字,不知道各位去思考了么? 面试题:数组中...

南尘
08/02
0
0
面试 19:输出数组中出现次数超过一半的数字(剑指 Offer 26 题)

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

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

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

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

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

繁著
07/26
0
0
剑指offer之数组中出现的次数

题目 一个整型数组里面除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(N),空间复杂度是O(1)。 2. 思路 首先,可以想一下,如果数组中只有一...

firepation
10/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

十月开源项目推荐:专为 Python 初学者准备的 IDE 你用过吗?

每月新增开源项目。顾名思义,每月更新一期。我们会从社区上个月新收录的开源项目中,挑选出有价值的、有用的、优秀的、或者好玩的开源项目来和大家分享。数量不多,但我们力求推荐的都是精品...

编辑部的故事
12分钟前
6
0
Java/Android 获取文件夹的文件列表(file.listFiles())并按名称排序,中文优先

排序规则 因为是中国人,习惯性看中文文件夹放前面比较顺眼,所以在别人博客(https://blog.csdn.net/da_caoyuan/article/details/56664673)的基础上,加上了自己的排序规则。 默认排序规则...

她叫我小渝
13分钟前
0
0
RabbitMQ通过shovel插件迁移数据

前言 生产环境中会遇到RabbitMQ数据迁移的场景,例如:切换云服务厂商、不同Region之间数据迁移、新搭建RabbitMQ实例,数据需要同步至新的RabbitMQ实例。 前提条件: 源RabbitMQ实例打开了s...

中间件小哥
16分钟前
0
0
kubernetes 环境搭建

kubernetes 简介:Kubernetes是一个开源的,用于管理云平台中多个主机上的容器化的应用,Kubernetes的目标是让部署容器化的应用简单并且高效(powerful)。 点击此处查看官网详情。...

MrPei
31分钟前
1
0
关于scala macro的example

http://www.bbartosz.com/blog/2016/09/24/fun-with-scalameta-examples-part1/

Littlebox
32分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部