面试中的集合算法题

约定不等于承诺〃 2023-07-10 12:40 25阅读 0赞

1.使用Set 确保集合元素的唯一性

public void test(){ 
                Set <Integer>set =new HashSet<>();
                 
                 while(set.size()!=10)
                 {
                        int a =(int)(Math.random()*100+1);
                        set.add(a);
                        
                 }
                 
                 
                 for(int b :set)
                 {
                        
                        System.out.println(b);
                 }
    }

2.从1、2、3…n找到其中缺失的那个  
解决思路：  
采用二分法的思想进行寻找  
其时间复杂度为 logn 空间复杂度为n

public class ListForTest {
    
        public static void main(String[] args) {
            ArrayList arrayList =new ArrayList<>();
            arrayList.add(0);
            arrayList.add(1);
            arrayList.add(3);
            //arrayList.add(4);
            test(arrayList);
        }
    
    
        /**
         * 从一组 1、2、3...递增的数组 找到缺失的
         */
        public static void test( ArrayList arrayList){
    
    
            int sum=0;
            if(arrayList.size()>1) {
                for (int i = 0; i <= (arrayList.size() - 1) / 2; i++) {
                    sum = sum + (int)arrayList.get(i);
                }
            }
            if (arrayList.size()==2){
               if((int)arrayList.get(1)-(int)arrayList.get(0) !=1){
                   System.out.println("缺少的数是"+ ((int)arrayList.get(0)+1));
               }
                return;
            }
    
    
            int length=arrayList.size();
            float allsum=0;
            if(length==1){
                allsum=(int)arrayList.get(0);
            }else {
                //这里存在 0、1除2等于0的情况
                if(length%2==0){
                    allsum=(float)(length/2)*((int)arrayList.get(0)+(int)arrayList.get((length-1)/2))/2;
                }else {
                    allsum=(float)(length/2+1)*((int)arrayList.get(0)+(int)arrayList.get((length-1)/2))/2;
                }
            }
            if(sum == allsum){
                if(length%2==0){
                    test(test3(arrayList,(arrayList.size())/2,length-1));
                }else {
                    test(test3(arrayList,(arrayList.size()-1)/2,length-1));
                }
    
    
            }else if (sum != allsum){
                    test( test3(arrayList,0,(arrayList.size()-1)/2));
            }
        }
    
        /**
         * 截取数组
         */
       public  static ArrayList test3(ArrayList input,int start,int end){
           ArrayList list = new ArrayList();
            int size=end-start+1;
            for(int i=0;i<size;i++){
            list.add(input.get(start+i));
            }
            return list;
       }
    }

3.从0…n中找到2个数，和为m  
解决思路：  
1.借助hash映射的方式  
2.其时间复杂度为n，空间复杂度也为n

/**
    * 从一组数组找到2个数和位m
    *
    *利用hash的方式 比如 2、7、11、15 求和13
    * 第一步  放入（0.2） 判断有没有 11 并没有
    * 第二步  放入（1,7） 判断有没有 6 并没有
    * 第三步  放入（2,11）判断有没有 2 有 输出结果
    *
    */
    class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i< nums.length; i++) {
                if(map.containsKey(target - nums[i])) {
                    return new int[] {map.get(target-nums[i]),i};
                }
                map.put(nums[i], i);
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    }

4.从数组找到重复出现两次的元素  
解决思路：  
1.使用hash来实现  
2.其时间复杂度为n,空间复杂度也为n  
3.Entry是map通过迭代器获取的数据类型，其既包含key和value

/**
    * 从一组数组找到重复出现两次的
    * 借助Entry 可以同时获得hash的key和value
    * 这里key是数字 value是数字出现的次数
    */
    public static void test2(Arrays arrays){
        int value = 0;
        int[] aa = { 1, 2, 3, 4, 5, 2, 3, 4, 2 };
        Map<Integer, Integer> m = new LinkedHashMap<Integer, Integer>();
        // 将每个数字对应的个数放入map
        for (int i = 0; i < aa.length; i++) {
            if (m.containsKey(aa[i])) {
                m.put(aa[i], ((Integer) m.get(aa[i])) + 1);
            } else {
                m.put(aa[i], 1);
            }
        }
        // 遍历map
        Iterator<Map.Entry<Integer, Integer>> it = m.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<Integer, Integer> entry = it.next();
            if (entry.getValue() == 2) {
                value = entry.getKey();
                break;
            }
        }
        System.out.println(value);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200812233234936.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA==,size_16,color_FFFFFF,t_70#pic_center