文档章节

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

aqia358
 aqia358
发布于 2013/10/17 13:28
字数 707
阅读 59
收藏 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
海淀
程序员
私信 提问
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
前天
0
0
面试 19:输出数组中出现次数超过一半的数字(剑指 Offer 26 题)

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

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

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

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

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

繁著
2018/09/05
0
0
剑指offer之数组中出现的次数

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

firepation
2018/10/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 白掌柜说了卖货不卖身

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @爱漫爱 :这是一场修行分享羽肿的单曲《Moony》 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :开不开心? 开心呀, 我又不爱睡懒觉…...

小小编辑
今天
9
0
大数据教程(11.7)hadoop2.9.1平台上仓库工具hive1.2.2搭建

上一篇文章介绍了hive2.3.4的搭建,然而这个版本已经不能稳定的支持mapreduce程序。本篇博主将分享hive1.2.2工具搭建全过程。先说明:本节就直接在上一节的hadoop环境中搭建了! 一、下载apa...

em_aaron
今天
3
0
开始看《JSP&Servlet学习笔记》

1:WEB应用简介。其中1.2.1对Web容器的工作流程写得不错 2:编写Servlet。搞清楚了Java的Web目录结构,以及Web.xml的一些配置作用。特别是讲了@WebServlet标签 3:请求与响应。更细致的讲了从...

max佩恩
今天
4
0
mysql分区功能详细介绍,以及实例

一,什么是数据库分区 前段时间写过一篇关于mysql分表的的文章,下面来说一下什么是数据库分区,以mysql为例。mysql数据库中的数据是以文件的形势存在磁盘上的,默认放在/mysql/data下面(可...

吴伟祥
今天
5
0
SQL语句查询

1.1 排序 通过order by语句,可以将查询出的结果进行排序。放置在select语句的最后。 格式: SELECT * FROM 表名 ORDER BY 排序字段ASC|DESC; ASC 升序 (默认) DESC 降序 1.查询所有商品信息,...

stars永恒
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部