当前位置： 首页 > news >正文

算法笔记_035:寻找最小的k个数（Java）

news 来源：原创 2024/5/8 8:12:28

目录

1 问题描述

2 解决方案

2.1 全部排序法

2.2 部分排序法

2.3 用堆代替数组法

2.4线性选择算法

 

1 问题描述

有n个整数，请找出其中最小的k个数，要求时间复杂度尽可能低。

 

2 解决方案

2.1 全部排序法

先对这n个整数进行快速排序，在依次输出前k个数。

具体代码如下：

package com.liuzhen.array_2;

public class SearchMinK {
    //方法1：全部排序
    public void quickSort(int[] A,int start,int end){
        if(end > start){
            int k = LomutoPartition(A,start,end);
            quickSort(A,start,k-1);
            quickSort(A,k+1,end);
        }
    }
    //返回数值result，满足：     左边部分< A[result] <=右边部分
    public int LomutoPartition(int[] A,int start,int end){
        if(start >= end)
            return start;
        int begin = A[start];
        int result = start;
        for(int i = start + 1;i <= end;i++){
            if(A[i] < begin){
                result++;
                swap(A,i,result);
            }
        }
        swap(A,start,result);
        return result;
    }
    //交换数组m位置和n位置上的值
    public void swap(int[] arrayA,int m,int n){
        int temp = arrayA[m];
        arrayA[m] = arrayA[n];
        arrayA[n] = temp;
    }
    //输出数组前k个元素
    public void printArrayK(int[] array,int k){
        for(int i = 0;i < k;i++){
            System.out.print(array[i]+" ");
        }
    }
public static void main(String[] args){
        SearchMinK test = new SearchMinK();
        int[] A = {9,8,7,5,4,3,2,1,6,3,4,5,12,32,3,2,1,4,6,34};
        test.quickSort(A, 0, A.length-1);
        System.out.println("对数组进行排序后结果：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
        System.out.println("\n"+"输出数组最小的5个数：");
        test.printArrayK(A, 5);

    }
}

运行结果：

对数组进行排序后结果：
1 1 2 2 3 3 3 4 4 4 5 5 6 6 7 8 9 12 32 34 
输出数组最小的5个数：
1 1 2 2 3

 

2.2 部分排序法

具体操作步骤如下：

（1）遍历n个数，把最先遍历到的k个数存入到大小为k的数组中，假设他们就是最小的k个数；

（2）利用选择排序或交换排序找到这k个元素中的最大值kmax；

（3）继续遍历剩余的n-k个数。假设每次遍历到的新元素的值为x,把x与kmax进行比较：如果x<kmax，则用x替换kmax，并回到第2步重新找出k个元素的数组中新的最大元素kmax;如果x>=kmax，则继续遍历，不更新数组。

具体代码如下：

package com.liuzhen.array_2;

public class SearchMinK {
//方法2：部分排序
    public void getArrayMinK(int[] A,int k){
        if(k > A.length)
            return;
        while(true){
            int max = getMaxArrayK(A,k);  //当前数组前k个元素中的最大值
            int count = 0;
            for(int i = k;i < A.length;i++){
                if(A[max] > A[i])
                    swap(A,max,i);
                else
                    count++;
            }
            if(count == A.length-k)
                break;
        }
        System.out.println("\n"+"使用方法2进行部分排序后的结果：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
        System.out.println("\n部分排序选出数组中最小的"+k+"个数：");
        for(int i = 0;i < k;i++)
            System.out.print(A[i]+" ");
    }
    
    //获取数组前k个元素的最大值的数组下标
    public int getMaxArrayK(int[] A,int k){
        int result = 0;
        if(k > A.length)
            return 0;
        for(int i = 0;i < k;i++){
            if(A[i] > A[result])
                result = i;
        }
        return result;
    }
//交换数组m位置和n位置上的值
    public void swap(int[] arrayA,int m,int n){
        int temp = arrayA[m];
        arrayA[m] = arrayA[n];
        arrayA[n] = temp;
    }
public static void main(String[] args){
        SearchMinK test = new SearchMinK();

        int[] B = {9,8,7,5,4,3,2,1,6,3,4,5,12,32,3,2,1,4,6,34};
        test.getArrayMinK(B, 5);

    }

运行结果：

使用方法2进行部分排序后的结果：
1 1 2 2 3 9 8 7 6 5 4 5 12 32 4 3 3 4 6 34 
部分排序选出数组中最小的5个数：
1 1 2 2 3

 

2.3 用堆代替数组法

此处思想和2.2中一致，唯一区别就是在寻找kmax时，是使用堆排序的思想。

具体代码如下：

package com.liuzhen.array_2;

public class SearchMinK {
//方法3：用堆来代替数组
    /*
     * 函数功能：对数组A前k个元素进行堆排序
     */
    public void heapBottomUp(int[] A,int k){
        for(int i = (k-1)/2;i >= 0;i--){
            int temp = i;
            int tempV = A[temp];
            boolean heap = false;
            while(!heap && 2*temp < k-1){
                int j = 2*temp + 1;
                if(j < k-1){
                    if(A[j] < A[j+1])
                        j = j + 1;
                }
                if(tempV >= A[j])
                    heap = true;
                else{
                    A[temp] = A[j];
                    temp = j;
                }
            }
            A[temp] = tempV;
        }
    }
    
    public void getArrayMinK2(int[] A,int k){
        heapBottomUp(A,k);
        while(true){
            int count = 0;
            for(int i = k;i < A.length;i++){
               if(A[i] < A[0]){
                   swap(A,i,0);
                  heapBottomUp(A,k);
               }
               else
                   count++;
            }
            if(count == A.length-k)
                break;
        }
        System.out.println("\n"+"使用方法3进行部分堆排序后的结果：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
        System.out.println("\n部分排序选出数组中最小的"+k+"个数：");
        for(int i = 0;i < k;i++)
            System.out.print(A[i]+" ");
    }
//交换数组m位置和n位置上的值
    public void swap(int[] arrayA,int m,int n){
        int temp = arrayA[m];
        arrayA[m] = arrayA[n];
        arrayA[n] = temp;
    }
public static void main(String[] args){
        SearchMinK test = new SearchMinK();

        int[] D = {9,8,7,5,4,3,2,1,6,3,4,5,12,32,3,2,1,4,6,34};
        test.getArrayMinK2(D, 5);

    }
}

运行结果：

使用方法3进行部分堆排序后的结果：
3 2 2 1 1 9 8 7 6 5 4 5 12 32 4 3 3 4 6 34 
部分排序选出数组中最小的5个数：
3 2 2 1 1

 

2.4线性选择算法

看具体代码即可理解其中蕴含的思想。

具体代码如下：

package com.liuzhen.array_2;

public class SearchMinK {
//返回数值result，满足：     左边部分< A[result] <=右边部分
    public int LomutoPartition(int[] A,int start,int end){
        if(start >= end)
            return start;
        int begin = A[start];
        int result = start;
        for(int i = start + 1;i <= end;i++){
            if(A[i] < begin){
                result++;
                swap(A,i,result);
            }
        }
        swap(A,start,result);
        return result;
    }

    //方法4：线性选择法
    public void getArrayMinK3(int[] A,int k){
        int start = 0;
        int end = A.length - 1;
        int tempK = LomutoPartition(A,start,end);
        while(tempK != k){
            if(tempK > k){
                end = tempK - 1;
                tempK = LomutoPartition(A,start,end);
            }
            if(tempK < k){
                start = tempK + 1;
                tempK = LomutoPartition(A,start,end);
            }
        }
        System.out.println("\n"+"使用方法4进行快速选择排序后的结果：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
        System.out.println("\n部分排序选出数组中最小的"+k+"个数：");
        for(int i = 0;i < k;i++)
            System.out.print(A[i]+" ");
    }
public static void main(String[] args){
        SearchMinK test = new SearchMinK();

        int[] E = {9,8,7,5,4,3,2,1,6,3,4,5,12,32,3,2,1,4,6,34};
        test.getArrayMinK3(E, 5);
    }
}

运行结果：

使用方法4进行快速选择排序后的结果：
1 2 2 1 3 3 3 4 5 5 4 4 6 8 6 7 9 32 12 34 
部分排序选出数组中最小的5个数：
1 2 2 1 3

 

附4种方法完整代码：

package com.liuzhen.array_2;

public class SearchMinK {
    //方法1：全部排序
    public void quickSort(int[] A,int start,int end){
        if(end > start){
            int k = LomutoPartition(A,start,end);
            quickSort(A,start,k-1);
            quickSort(A,k+1,end);
        }
    }
    //返回数值result，满足：     左边部分< A[result] <=右边部分
    public int LomutoPartition(int[] A,int start,int end){
        if(start >= end)
            return start;
        int begin = A[start];
        int result = start;
        for(int i = start + 1;i <= end;i++){
            if(A[i] < begin){
                result++;
                swap(A,i,result);
            }
        }
        swap(A,start,result);
        return result;
    }
    //交换数组m位置和n位置上的值
    public void swap(int[] arrayA,int m,int n){
        int temp = arrayA[m];
        arrayA[m] = arrayA[n];
        arrayA[n] = temp;
    }
    //输出数组前k个元素
    public void printArrayK(int[] array,int k){
        for(int i = 0;i < k;i++){
            System.out.print(array[i]+" ");
        }
    }
    
    //方法2：部分排序
    public void getArrayMinK(int[] A,int k){
        if(k > A.length)
            return;
        while(true){
            int max = getMaxArrayK(A,k);  //当前数组前k个元素中的最大值
            int count = 0;
            for(int i = k;i < A.length;i++){
                if(A[max] > A[i])
                    swap(A,max,i);
                else
                    count++;
            }
            if(count == A.length-k)
                break;
        }
        System.out.println("\n"+"使用方法2进行部分排序后的结果：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
        System.out.println("\n部分排序选出数组中最小的"+k+"个数：");
        for(int i = 0;i < k;i++)
            System.out.print(A[i]+" ");
    }
    
    //获取数组前k个元素的最大值的数组下标
    public int getMaxArrayK(int[] A,int k){
        int result = 0;
        if(k > A.length)
            return 0;
        for(int i = 0;i < k;i++){
            if(A[i] > A[result])
                result = i;
        }
        return result;
    }
    
    //方法3：用堆来代替数组
    /*
     * 函数功能：对数组A前k个元素进行堆排序
     */
    public void heapBottomUp(int[] A,int k){
        for(int i = (k-1)/2;i >= 0;i--){
            int temp = i;
            int tempV = A[temp];
            boolean heap = false;
            while(!heap && 2*temp < k-1){
                int j = 2*temp + 1;
                if(j < k-1){
                    if(A[j] < A[j+1])
                        j = j + 1;
                }
                if(tempV >= A[j])
                    heap = true;
                else{
                    A[temp] = A[j];
                    temp = j;
                }
            }
            A[temp] = tempV;
        }
    }
    
    public void getArrayMinK2(int[] A,int k){
        heapBottomUp(A,k);
        while(true){
            int count = 0;
            for(int i = k;i < A.length;i++){
               if(A[i] < A[0]){
                   swap(A,i,0);
                  heapBottomUp(A,k);
               }
               else
                   count++;
            }
            if(count == A.length-k)
                break;
        }
        System.out.println("\n"+"使用方法3进行部分堆排序后的结果：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
        System.out.println("\n部分排序选出数组中最小的"+k+"个数：");
        for(int i = 0;i < k;i++)
            System.out.print(A[i]+" ");
    }
    
    //方法4：线性选择法
    public void getArrayMinK3(int[] A,int k){
        int start = 0;
        int end = A.length - 1;
        int tempK = LomutoPartition(A,start,end);
        while(tempK != k){
            if(tempK > k){
                end = tempK - 1;
                tempK = LomutoPartition(A,start,end);
            }
            if(tempK < k){
                start = tempK + 1;
                tempK = LomutoPartition(A,start,end);
            }
        }
        System.out.println("\n"+"使用方法4进行快速选择排序后的结果：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
        System.out.println("\n部分排序选出数组中最小的"+k+"个数：");
        for(int i = 0;i < k;i++)
            System.out.print(A[i]+" ");
    }
    public static void main(String[] args){
        SearchMinK test = new SearchMinK();
        int[] A = {9,8,7,5,4,3,2,1,6,3,4,5,12,32,3,2,1,4,6,34};
        test.quickSort(A, 0, A.length-1);
        System.out.println("对数组进行排序后结果：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
        System.out.println("\n"+"输出数组最小的5个数：");
        test.printArrayK(A, 5);
        int[] B = {9,8,7,5,4,3,2,1,6,3,4,5,12,32,3,2,1,4,6,34};
        test.getArrayMinK(B, 5);
        int[] C = {2,9,7,6,5,8};
        test.heapBottomUp(C, 6);
        System.out.println("\nC数组：");
        for(int i = 0;i < C.length;i++)
            System.out.print(C[i]+" ");
        int[] D = {9,8,7,5,4,3,2,1,6,3,4,5,12,32,3,2,1,4,6,34};
        test.getArrayMinK2(D, 5);
        int[] E = {9,8,7,5,4,3,2,1,6,3,4,5,12,32,3,2,1,4,6,34};
        test.getArrayMinK3(E, 5);
    }
}
完整代码

 

相关文章：

  • Linux 文件系统 的 学习
  • eclipse中内存溢出java.lang.OutOfMemoryError: PermGen space解决
  • Webpack入门教程十八
  • keepalived工作原理和配置说明
  • BZOJ 4031: [HEOI2015]小Z的房间 [矩阵树定理 行列式取模]
  • centos7下安装samba服务器
  • DJ下载工具|DJ格式转换工具|剪切工具_已迁移
  • springMVC启动时,加载数据至内存中配置详解;
  • HTTP笔记（一）
  • Nginx开启OCSP Stapling
  • linux学习笔记
  • Linux常用命令——挂载 mount
  • 【SGE】任务显示 T 状态，qstat -j 报错 can not find an unused add_grp_id
  • NTP server
  • nginx访问控制
  • 9月CHINA-PUB-OPENDAY技术沙龙——IPHONE
  • android高仿小视频、应用锁、3种存储库、QQ小红点动画、仿支付宝图表等源码...
  • CentOS6 编译安装 redis-3.2.3
  • codis proxy处理流程
  • git 常用命令
  • Java教程_软件开发基础
  • Laravel 中的一个后期静态绑定
  • MyEclipse 8.0 GA 搭建 Struts2 + Spring2 + Hibernate3 （测试）
  • MySQL-事务管理（基础）
  • vue-router 实现分析
  • yii2权限控制rbac之rule详细讲解
  • 机器人定位导航技术 激光SLAM与视觉SLAM谁更胜一筹？
  • 快速构建spring-cloud+sleuth+rabbit+ zipkin+es+kibana+grafana日志跟踪平台
  • 思考 CSS 架构
  • 限制Java线程池运行线程以及等待线程数量的策略
  • 3月7日云栖精选夜读 | RSA 2019安全大会：企业资产管理成行业新风向标，云上安全占绝对优势 ...
  • # Java NIO（一）FileChannel
  • $.type 怎么精确判断对象类型的 --（源码学习2）
  • $con= MySQL有关填空题_2015年计算机二级考试《MySQL》提高练习题(10)
  • （Redis使用系列） SpringBoot 中对应2.0.x版本的Redis配置 一
  • （二）Linux——Linux常用指令
  • （附源码）springboot 校园学生兼职系统 毕业设计 742122
  • （经验分享）作为一名普通本科计算机专业学生，我大学四年到底走了多少弯路
  • (原創) 如何刪除Windows Live Writer留在本機的文章? (Web) (Windows Live Writer)
  • ***php进行支付宝开发中return_url和notify_url的区别分析
  • *Algs4-1.5.25随机网格的倍率测试-(未读懂题)
  • .bat批处理（十）：从路径字符串中截取盘符、文件名、后缀名等信息
  • .NET : 在VS2008中计算代码度量值
  • .NET C#版本和.NET版本以及VS版本的对应关系
  • .NET Framework 和 .NET Core 在默认情况下垃圾回收（GC）机制的不同（局部变量部分）
  • .NET Project Open Day(2011.11.13)
  • .NET 材料检测系统崩溃分析
  • .NET 的程序集加载上下文
  • .Net 路由处理厉害了
  • .NET处理HTTP请求
  • .Net的C#语言取月份数值对应的MonthName值
  • .Net高阶异常处理第二篇~~ dump进阶之MiniDumpWriter
  • .NET是什么
  • .NET委托：一个关于C#的睡前故事
  • [2016.7 day.5] T2