剑指offer练习题：数组中的重复数字

剑指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--;
                }
            }


        }
    }

}