剑指offer:数组中重复的数字

旧城等待， 2022-11-15 11:16 179阅读 0赞

**题目描述  
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组\[2,3,1,0,2,5,3\]，那么对应的输出是2或者3。存在不合法的输入的话输出-1  
输入:\[2,3,1,0,2,5,3\]  
输出:2或3**

思路:(1)先判断数组是否合法,不合法直接返回-1.  
(2)对数组进行排序  
(3)遍历数组,将数字和数字出现的次数存储在HashMap中  
(4)遍历HashMap,将Value值大于1的key值返回即可.

import java.util.*;
    
    
    public class Solution { 
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param numbers int整型一维数组 
         * @return int整型
         */
        public int duplicate (int[] numbers) { 
            // write code here
            if(numbers.length==0 || numbers==null){ 
                return -1;
            }
            Arrays.sort(numbers);
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();
            for(int i =0;i<numbers.length;i++){ 
                if(!map.containsKey(numbers[i])){ 
                    map.put(numbers[i],1);
                }else{ 
                    int value = map.get(numbers[i])+1;
                    map.put(numbers[i],value);
                }
            }
            Iterator<Map.Entry<Integer,Integer>> entries = map.entrySet().iterator();
            while(entries.hasNext()){ 
                Map.Entry<Integer,Integer> entry = entries.next();
                if(entry.getValue()>1) return entry.getKey();
            }
            return -1;
        }
    }

在做这一题的时候,顺便复习了一下HashMap的遍历方式,在此也做个记录:

import java.util.*;
    
    public class TestHashMap{ 
        public static void main(String[] args) { 
            Map<String,Integer> hashmap = new HashMap<>();
            hashmap.put("张三",12);
            hashmap.put("李四",15);
            //1.entry实现遍历
            System.out.println("======通过entrySet实现迭代=====");
            for (Map.Entry<String,Integer> entry: hashmap.entrySet()){ 
                System.out.println("entry:"+entry);
            }
            //2.通过键迭代
            System.out.println("=====通过键迭代======");
            for(String str :hashmap.keySet()){ 
                System.out.println(str);
            }
            //3.通过value实现迭代
            System.out.println("========通过Value来实现迭代======");
            for (Integer i: hashmap.values()){ 
                System.out.println(i);
            }
            System.out.println("======使用带泛型的迭代器进行遍历=========");
            Iterator<Map.Entry<String,Integer>> entries = hashmap.entrySet().iterator();
            while (entries.hasNext()){ 
                Map.Entry<String,Integer> entry =  entries.next();
                System.out.println("key="+entry.getKey()+";"+"value="+entry.getValue());
            }
    
        }
    
    }