美文网首页
java 数组算法

java 数组算法

作者: Bfmall | 来源:发表于2023-03-23 14:05 被阅读0次

    1.给定一个 1-100 的整数数组,请找到其中缺少的数字

    思路:利用hashmap,首先将100个数字存入map中,value初始为0;然后遍历数组,找到一个数字,把value更新为1,这样遍历完成后,就找到了那个缺少的数字了。

        /**
         *  如何在一个1到100的整数数组中找到丢失的数字
         */
        public void test01(int[] arr) {
            //初始化map,将1-100都放到map里面,value初值为0
            Map<Integer, Integer> map = new HashMap<>();
            for (int i=1;i<=100;i++) {
                map.put(i, 0);
            }
    
            //遍历数组,找到一个数字,就更新对应的vaule为1
            for (int i=0;i<arr.length;i++) {
                map.put(arr[i], 1);
            }
            
            //遍历map,如果发现value为0,则找到丢失的数字了,返回
            Set<Map.Entry<Integer, Integer>> set = map.entrySet();
            Iterator iter = set.iterator();
            while (iter.hasNext()) {
                Map.Entry<Integer, Integer> entry = (Map.Entry<Integer, Integer>) iter.next();
                if (entry.getValue() == 0) {
                    System.out.println("missing value="+entry.getKey());
                }
            }
        }
    

    测试代码:

        public void test() {
            List<Integer> list=new ArrayList<>();
            int[] arr=new int[99];
            Random rd=new Random();
            //随机生成长度99的数组,不包含重复数字
            while(list.size()<99){
                int a=rd.nextInt(100)+1;
                if(!list.contains(a)){
                    list.add(a);
                }
            }
            //将list中的值赋给数组
            for(int i=0;i<99;i++){
                arr[i]=list.get(i);
            }
            //将数组排序,以便观察检验
            Arrays.sort(arr);
            test01(arr);
        }
    

    2.如何在未排序整数数组中找到最大值和最小值?

    思路:创建两个变量 max 和 min 分别记录数组中的最大值和最小值,它们的初始值都是数组中的第一个数字。从第 2 个数字开始遍历数组,每遇到一个比 max 大的数字,就将它存储到 max 变量中;每遇到一个比 min 小的数字,就将它存储到 min 变量中。直到遍历完整个数组,max 记录的就是数组中的最大值,min 记录的就是数组中的最小值。

        /**
         * 如何在未排序整数数组中找到最大值和最小值?
         * //int[] arr = {8,9,3,1,5,6,10};
         * @param arr
         */
        public void test02(int[] arr) {
            int min;
            int max;
            if (arr != null && arr.length > 0) {
                min = arr[0];
                max = arr[0];
                for (int i=1;i<arr.length;i++) {
                    if (arr[i] < min) {
                        min = arr[i];
                    }
                    if (arr[i] > max) {
                        max = arr[i];
                    }
                }
                System.out.println("min="+min+", max="+max);
            }
        }
    

    3.给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。要求:空间复杂度O(1),时间复杂度为O(n)

    思路:
    分别从数组两端向中间推进,推出条件为左右相撞。
    当左端值为偶数,并且右端值为奇数时交换二值,用到一个临时空间。
    当左端值为奇数,向右推进一个单位。
    当右端值为偶数,向左推进一个单位。

    3.1实现代码:

    /**
         * 给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。要求:空间复杂度O(1),时间复
         * 杂度为O(n)。
         * //int[] arr = {8,9,3,1,5,6,10};
         * 输出结果:
         * 排序后的数组:[5, 9, 3, 1, 8, 6, 10]
         */
        public void test03(int[] arr) {
            if (arr != null && arr.length > 0) {
                int i = 0;
                int j = arr.length - 1;
                int temp;
                while (i < j) {
                    if (isEvenNumber(arr[i]) && !isEvenNumber(arr[j])) {
                        //需要交换位置
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
    
                    if (!isEvenNumber(arr[i])) {
                        //如果arr[i]是奇数,i向右移动
                        i ++;
                    }
    
                    if (isEvenNumber(arr[j])) {
                        //如果arr[j]是偶数,j向左移动
                        j --;
                    }
                }
                System.out.println("排序后的数组:"+Arrays.toString(arr));
            }
        }
    
        /**
         * 是否是偶数
         * @param num
         * @return
         */
        private boolean isEvenNumber(int num) {
            return num % 2 == 0;
        }
    

    测试代码:

    int[] arr2 = {8,9,3,1,5,6,10};
    test03(arr2);
    

    测试结果:

    排序后的数组:[5, 9, 3, 1, 8, 6, 10]
    

    可以看到输出结果中奇数在左边,偶数在右边,但打乱了顺序,下面对奇数和偶数分别进行从小到大排列

    3.2实现代码(对奇数和偶数两组数据分别进行从小到大排列):

    public void test04(int[] arr) {
            if (arr != null && arr.length > 0) {
                List<Integer> oddList = new ArrayList<>();//奇数list
                List<Integer> evenList = new ArrayList<>();//偶数list
                int i = 0;
                int j = arr.length - 1;
                int temp;
                while (i < j) {
                    if (isEvenNumber(arr[i]) && !isEvenNumber(arr[j])) {
                        //需要交换位置
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
    
                    if (!isEvenNumber(arr[i])) {
                        //如果arr[i]是奇数,i向右移动
                        i ++;
                    }
    
                    if (isEvenNumber(arr[j])) {
                        //如果arr[j]是偶数,j向左移动
                        j --;
                    }
                }
                for (int m=0;m<arr.length;m++) {
                    if (isEvenNumber(arr[m])) {
                        //偶数
                        evenList.add(arr[m]);
                    } else {
                        //奇数
                        oddList.add(arr[m]);
                    }
                }
                Collections.sort(oddList);
                Collections.sort(evenList);
    
                List<Integer> newList = new ArrayList<>();
                newList.addAll(oddList);
                newList.addAll(evenList);
    
                Log.i(TAG, "排序后的数组:"+newList.toString());
                System.out.println("排序后的数组:"+newList.toString());
            }
        }
    
        /**
         * 是否是偶数
         * @param num
         * @return
         */
        private boolean isEvenNumber(int num) {
            return num % 2 == 0;
        }
    

    4.在Java中如何从给定排序数组中删除重复项?

    问题简述:
    给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

    由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。

    将最终结果插入 nums 的前 k 个位置后返回 k 。

    不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    参考:https://blog.csdn.net/weixin_46703995/article/details/127849601

    /**
         * 在Java中如何从给定排序数组中删除重复项?
         * @param arr
         * @return 返回新数组的长度(忽略原有数组的长度)
         */
        public int removeDuplicates(int[] arr) {
            if (arr.length <= 1) {
                return arr.length;
            }
            int slow = 0;
            /**
             * 原始数组:int[] arr3 = {1,3,3,5,6,6,8};
             * 第一步:slow = 0, fast = 1 -> slow = 1; arr[slow]=3; -> 结果:arr3= {1,3,3,5,6,6,8};
             * 第二步:slow = 1, fast = 2 -> slow = 1; arr[slow]=3; -> 结果:arr3= {1,3,3,5,6,6,8};没变化
             * 第三步:slow = 1, fast = 3 -> slow = 2; arr[slow]=5; -> 结果:arr3= {1,3,5,5,6,6,8};
             * 第四步:slow = 2, fast = 4 -> slow = 3; arr[slow]=6; -> 结果:arr3= {1,3,5,6,6,6,8};
             * 第五步:slow = 3, fast = 5 -> slow = 3; arr[slow]=6; -> 结果:arr3= {1,3,5,6,6,6,8};没变化
             * 第六步:slow = 3, fast = 6 -> slow = 4; arr[slow]=8; -> 结果:arr3= {1,3,5,6,8,6,8};
             */
            for (int fast = 1;fast < arr.length;fast++) {
                if (arr[slow] != arr[fast]) {
                    slow ++;
                    arr[slow] = arr[fast];
                }
            }
            return slow + 1;
        }
    

    测试代码:

    int[] arr = {1,3,3,5,6,6,8};
    int newArrLength=removeDuplicates(arr);
    Log.i(TAG, "arr="+Arrays.toString(arr)+", arrLength="+newArrLength);
    

    结果:

    arr=[1, 3, 5, 6, 8, 6, 8], newArrLength=5
    其中新数组内容为数组的前5位,即[1,3,5,6,8]
    

    相关文章

      网友评论

          本文标题:java 数组算法

          本文链接:https://www.haomeiwen.com/subject/gbmmrdtx.html