剑指offer练习题：数组中的重复数字
思路一:利用HashMap的特性，遍历数组如果没有在hashmap中存储的数字，则添加进hashmap,如果已经有该值存储在hashmap中，则表示该值重复：
package com.ajman;
import java.util.HashMap;
public class Top2 {
// 请在给出的整数数组中找到重复的数字
// 利用hashmap
public static void repeatnum(int[] nums){
// 重复的数字
HashMap<Integer,Integer> map=new HashMap();
for(int i=0;i<nums.length;i++){
if(map.containsValue(nums[i])){
System.out.println(nums[i]);
}else{
map.put(i,nums[i]);
}
}
}
public static void main(String[] args) {
int[] nums={1,2,3,3,2,2};
repeatnum(nums);
}
}
思路二：上面的哈希表法的时间复杂度是O（n）,空间复杂度是O（n）
现在我们重排这个数组，从头到尾依次扫描这个数组中的每个数字，当扫描到下标为i的数字（m）的时候，首先比较这个数字是不是等于i
如果是，则继续扫描下一位数字；
如果不是则跟下标为m的数字互相交换。如果他和第m个数字相同则表示找到相同的数字
- 以数组（2,3,1,0,2,5,3）为例，当扫描到0下标的数字2时，数字 下标0与数值2不相等，则我们可以进行交换操作，把下标为0的数字和下标为2的数字进行交换。结果是{1,3,2,0,2,5,3}，继续扫描0的下标，这次是数字1与下标0不相等，同样进行交换操作，得到数组{3,1,2,0,2,5,3}.接下来继续交换下标3的数字和下标0的数字，结果是{0,1,2,3,2,5,3}.此时第0个数字是0，则继续扫描下一位数字，发现1,2,3是不用交换的，当扫描下标为4的数字2的时候，下标为4的数字与下标为2的数字比较时，发现数字相同，则表示2重复了
package com.ajman;
public class Top2$1 {
// 同样是寻找数组中重复的数字，这是剑指offer的解法：
// 时间复杂度是O(N)，空间复杂度是O(1)
/**
* 现在我们重拍这个数组，从头到尾依次扫描这个数组中的每个数字，当扫描到下标为i的数字（m）的时候，首先比较这个数字是不是等于i
* 如果是，则继续扫描下一位数字；
* 如果不是则跟下标为m的数字互相交换。如果他和第m个数字相同则表示找到相同的数字
*/
public static void main(String[] args) {
int[] nums={1,2,2,3,3};
repeatnum(nums);
}
public static void repeatnum(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
System.out.println(nums[i]);
} else {
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
i--;
}
}
}
}
}
