剑指offer第二版面试题1:数组中重复的数字(JAVA版)
题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复的次数。请找出数组中任意一个重复的数字。例如如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。
为此题目提供三种想法,但是只实现书上的一种方法
1.先将数组排序,然后扫描数组就很容易得到重复的数字
2.利用HashSet,遍历数组,如果set中不存在数组中的值就直接放入set,否则就是重复数字
3.我们注意到数组中的数字都在0到n-1的范围内。如果这个数组中没有重复的数字,那么当数组排序后数字i将出现在下标为i的位置。由于数组中有重复的数字,有些位置可能存在多个数字,同时有些位置可能没有数字。现在让我们重排这个数组。从头到尾扫描这个数组中的每个数字。当扫描到下标为i的数字的时候,首先比较这个数字(用m表示)是不是i。如果是,接着扫描下一个数字。如果不是,再拿它和第m个数字进行比较。如果它和第m个数字相等,就找到一个重复的数字(该数字在下标为i和m的位置都出现了)。如果它和第m个数字不想等,就把第i个数字和第m个数字交换,把m放到属于它的位置。接下来再重复这个比较,交换的过程,直到发现一个重复的数字。以数组{2,3,1,0,2,5,3}为例来分析找到重复数字的步骤。数组的第0个数字(从0开始计数,和数组的下标保持一致)是2,与它的下标不相等,于是把它和下标为2的数字1交换,交换后的数组是{1,3,2,0,2,5,3}。此时第0 个数字是1,仍然与它的下标不相等,继续把它和下标为1的数字3交换,得到数组{0,1,2,3,2,5,3}。此时第0 个数字为0,接着扫描下一个数字,在接下来的几个数字中,下标为1,2,3的三个数字分别为1,2,3,他们的下标和数值都分别相等,因此不需要做任何操作。接下来扫描下标为4的数字2.由于它的值与它的下标不相等,再比较它和下标为2的数字。注意到此时数组中下标为2的数字也是2,也就是数字2和下标为2和下标4的两个位置都出现了,因此找到一个重复的数字。
代码如下:
public class Solution { public static int duplication; public static boolean duplicate(int[] arr) {
if (arr == null || arr.length == 0) {
return false;
} for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0 || arr[i] >= arr.length) {
return false;
}
} for (int i = 0; i < arr.length; i++) {
while (arr[i] != i) {
if (arr[i] == arr[arr[i]]) {
duplication = arr[i];
System.out.println(arr[i]);
return true;
} int temp = arr[i];
arr[i] = arr[temp];
arr[temp] = temp;
}
}
return false;
} public static void main(String[] args) {
int[] arr = { 0, 3, 1, 4, 2, 5, 7 };
boolean result = duplicate(arr);
System.out.println(result);
} }
最新文章
- TD Rigging Demo Reel 性感美女绑定展示
- HashMap LinkedHashMap源码分析笔记
- Beta版本冲刺Day2
- SQL调优
- AIX系统程序异常不释放光驱处理
- Android IOS WebRTC 音视频开发总结(五十)-- 技术服务如何定价?
- 利用dijkstra算法规划线路
- [转]SSL协议详解
- Unity 游戏框架搭建 (四) 简易有限状态机
- BZOJ_1029_ [JSOI2007]建筑抢修_贪心+堆
- ifconfig 网卡 下面的参数
- 基于SoftRoCE 了解RDMA
- POJ-3414.Pots.(BFS + 路径打印)
- [Python_2] Python 基础
- kubeadm安装K8S单master双节点集群
- POJ-3259 Wormholes(判断负环、模板)
- 【BZOJ2962】序列操作(线段树)
- jquery选择器用法笔记(第二部分)
- m2014-architecture-imgserver->;配置lighttpd mod_mem_cache 模块做静态资源服务器
- 教你使用markdown画程序流程图