JAVA中寻找最大的K个数解法

这个题拿到之后首先会想到排序，排好序之后在选取选取最大的K个数。排序选择快速排序是个比较好的选择。
好了，让我们来进行第一个解法：快速排序
代码如下


代码如下:

public static void quickSort(int[] arr, int start, int end) {
  if (start < end) {
   int key = arr[start];
   int right = start;
   int left = end;
   while (right < left) {
    while (right < left && arr[left] > key) {
     left --;
    }
    if (right < left) {
     arr[right] = arr[left];
    }
    while (right < left && arr[right] <= key) {
     right ++;
    }
    if (right < left) {
     arr[left] = arr[right];
    }
   }
   arr[right] = key;
   quickSort(arr, start, right-1);
   quickSort(arr, left+1, end);
  }
 }

快速排序之后，数组会是有序的，上面的排序是从小到大的，所以我们输出应该是下面这样


代码如下:

int k = 4;
  for (int i=arr.length-1; i>=arr.length-k; i--) {
   System.out.println(arr[i]+"  ");
  }

。第一个解法已经好了，但是有没有更好的办法。
答案是有的！我们可以选择部分排序，接下来我们使用选择排序来做解决这个问题。
代码如下：


代码如下:

public static int[] selectSortK(int[] arr, int k) {
  if(arr == null || arr.length == 0) {
   return null;
  }
  int[] newArr = new int[k];
  List<Integer> list = new ArrayList<Integer>();//记录每次最大数的下标
  for (int i=0; i<k; i++) {
   int maxValue = Integer.MIN_VALUE; //最大值
   int maxIndex = i;
   for (int j=0; j<arr.length; j++) {
    if (arr[j] > maxValue && !list.contains(j) ) {
     maxValue = arr[j];
     maxIndex = j;
    }
   }
   if (!list.contains(maxIndex)) {//如果不存在，就加入
    list.add(maxIndex);
    newArr[i] = maxValue;
   }
  }
  return newArr;
 }

赞 (0)

相关推荐

  • java识别一篇文章中某单词出现个数的方法

    本文实例讲述了java识别一篇文章中某单词出现个数的方法.分享给大家供大家参考.具体如下: 1. java代码: import java.io.DataInputStream; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.util.StringTokenizer; import java.util.regex.Matche

  • java实现单词搜索迷宫游戏

    本文实例讲述了java实现单词搜索迷宫游戏.分享给大家供大家参考.具体分析如下: 我们在杂志上,经常能够看到找单词的小游戏,在一个二维表格中,存在各种字母,我们可以从八个方向找单词.这个用计算机处理十分方便,但是,算法的好坏很重要,因为要是用蛮力算法实现,那么耗费的时间是不可想象的. 这是数据结构与问题求解Java语言描述一书中给的实现思路 完整代码如下,注释写的很明白了 import java.io.BufferedReader; import java.io.FileReader; impo

  • java求三个数的最大值的示例分享

    复制代码 代码如下: import java.util.Arrays; import java.util.Scanner; public class MaxOf3_2 { /* * 获取最大的整数 */     public static int getMaxNum(int...a){         Arrays.sort(a);         int maxNum = a[a.length-1];         return maxNum;     } }

  • java中实现递归计算二进制表示中1的个数

    借助Java语言,运用递归算法计算整数N的二进制表示中1的个数 /*use the recursive algorithme to calculate * the number of "1" in the binary expression * of an Integer N. * Note:if N is an odd, then * the result is the result of N/2 plus 1. * And the program use the bit opera

  • 利用java实现单词倒序排列

    本文就是会将数组里面的单词进行倒序排列 例如 how old are you -> you are old how 示例程序输出结果: the first: How old are you !? I don't understand the second: understand don't I ?! you are old How 示例代码 public static void main(String[] args) { char[] chars= new String("How old

  • java阶乘计算获得结果末尾0的个数代码实现

    看到题目后,分析了下, 10的阶乘就已经很大了.计算出来再得到这个末尾的0的个数,完全不现实,即使实现了也是很麻烦的. 后来想某个数的阶乘中乘积有5结尾的数字的时候就应该在结果的末尾产生一个0. 付诸实现,测试了几个, 没出错. 贴出来, 大家看看, 有问题了及时指教: 复制代码 代码如下: /**     * 求1000~10000之间的数n的阶层并计算所得的数n!末尾有多少个0?     */    public static void test2(int number){        i

  • JAVA中寻找最大的K个数解法

    这个题拿到之后首先会想到排序,排好序之后在选取选取最大的K个数.排序选择快速排序是个比较好的选择.好了,让我们来进行第一个解法:快速排序代码如下 复制代码 代码如下: public static void quickSort(int[] arr, int start, int end) {  if (start < end) {   int key = arr[start];   int right = start;   int left = end;   while (right < lef

  • Python实现从N个数中找到最大的K个数

    提出问题: 如何在某集合里面找出最大或最小的K个元素. 解决思路: 找出最大或最下的K个元素,可以使用Python库中的heapq模块,该模块提供两个函数nlargest()求最大K个和nsmallest()求最小K个. 下面我们举例说明: import heapq nums=[12,-9,-3,32,9,56,23,0,11,34] print(heapq.nlargest(4,nums)) #-->最大的4个 print(heapq.nsmallest(4,nums)) #-->最小的4个

  • Java C++题解 leetcode第k个数实例

    Java C++题解 leetcode第k个数实例

    目录 题目要求 思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结 题目要求 思路一:小根堆 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也

  • 最大K个数问题的Python版解法总结

    TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词. 方法一: 先排序,然后截取前k个数. 时间复杂度:O(n*logn)+O(k)=O(n*logn). 这种方式比较简单粗暴,提一下便是. 方法二:最大堆 我们可以创建一个大小为K的数据容器来存储最小的K个数,然后遍历整个数组,将每个数字和容器中的最大数进行比较,如果这个数大于容器中的最大值,则继续遍历,否则用这个数字替换掉容器中的最大值.这个方法的理解也十分简单,至于容器的选择,很多人第一反应便

  • Python实现查找最小的k个数示例【两种解法】

    本文实例讲述了Python实现查找最小的k个数.分享给大家供大家参考,具体如下: 题目描述 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,. 解法1 使用partition函数可以知道,使用==O(N)==的时间复杂度就可以找出第K大的数字,并且左边的数字比这个数小,右边的数字比这个数字大.因此可以取k为4,然后输出前k个数字,如果需要排序的话再对结果进行排序 # -*- coding:utf-8 -*- class So

  • java实现统计字符串中字符及子字符串个数的方法示例

    java实现统计字符串中字符及子字符串个数的方法示例

    本文实例讲述了java实现统计字符串中字符及子字符串个数的方法.分享给大家供大家参考,具体如下: 这里用java实现统计字符串中的字符(包括数字.大写字母.小写字母以及其他字符)个数,以及字符串的子字符串的个数. 运行效果图如下: 具体代码如下: import java.util.Scanner; public class Counter { static Scanner scanner = new Scanner(System.in); public static void count(Str

  • C语言实现两个递减数列中寻找某一个数

    C语言实现两个递减数列中寻找某一个数

    本文实例讲述了C语言实现两个递减数列中寻找某一个数的方法,分享给大家供大家参考之用.具体方法如下: 通常来说这道题算二分查找法中非常有难度的一题了. 题目如下: 一个数组是由一个递减数列左移若干位形成,比如{4, 3, 2, 1, 6, 5}是由{6, 5, 4, 3, 2, 1}左移两位,在这种数组中查找某一个数. 实现代码如下: int array[] = {4, 3, 2, 1, 6, 5}; const int size = sizeof array / sizeof *array; i

  • Java判断List中相同值元素的个数实例

    如下所示: Map<Object, Integer> map = new TreeMap<Object, Integer>(); for (Object i : listIp) { if (map.get(i) == null) { map.put(i, 1); } else { map.put(i, map.get(i) + 1); } } 以上这篇Java判断List中相同值元素的个数实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Java实现最小生成树MST的两种解法

    Java实现最小生成树MST的两种解法

    目录 一.prim算法 二.kruskal算法 一.prim算法 时间复杂度较之kruskal较高 通俗的解释就是: (1)从哪个点开始生成最小生成树都一样,最后的权值都是相同的 (2)从哪个点开始,先标记这个点是访问过的,用visited数组表示所有节点的访问情况 (3)访问节点开始都每个没访问结点的距离选取形成的边的权值最小值 综合以上三点就是我们prim算法写代码实现的重要思路 代码实现: package Prim; import java.util.Arrays; public clas

  • Java中List Set和Map之间的区别_动力节点Java学院整理

    Java集合的主要分为三种类型: • Set(集) • List(列表) • Map(映射) 要深入理解集合首先要了解下我们熟悉的数组: 数组是大小固定的,并且同一个数组只能存放类型一样的数据(基本类型/引用类型),而JAVA集合可以存储和操作数目不固定的一组数据. 所有的JAVA集合都位于 java.util包中! JAVA集合只能存放引用类型的的数据,不能存放基本数据类型. 世间上本来没有集合,(只有数组参考C语言)但有人想要,所以有了集合 有人想有可以自动扩展的数组,所以有了List 有的

随机推荐