Java算法篇在一个int数组中寻找最大的k个数字

背景

在一个int数组中,寻找最大的k个数字,时间复杂度是O(n)。

数组不大情况下

思路:

  • 类似于基本排序中的基数排序,利用空间换时间,待排序数组的值是新数组的索引,新数组的值就是出现的次数,考虑重复的情况
  • 新数组如果值为空,则表示这个索引值在原来数组根本不存在,如果大于1则该数字在原来数组出现多次

第一步:

找到原数组最大值,利用比较计算

第二步:

新建数组,size是第一步中的最大值+1;

第三步:

循环原来数组,利用temp[a[i]]++,计算索引表示的数字在原数组出现次数

第四步:

倒序遍历新的数组,如果元素值不为0,打印下标,循环打印,直到数组值为0,并计算打印的元素个数count++,直到count等于k,完成输出

package com.puhui.goosecard.web;

/**
 * 2 * @Author: kerry
 * 3 * @Date: 2018/9/6 19:45
 * 4
 */
public class Test {


    private static int searchMax(int[] temp) {
        int max = temp[0];
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] > max) {
                max = temp[i];
            }
        }
        return max;

    }


    public static void main(String[] args) {
        int[] a = {1, 4, 12, 8, 6, 98, 3, 4, 1, 12};
        int max = searchMax(a);
        int k = 5;
        //max加1否则是0-97,数组越界98
        int[] temp = new int[max + 1];
        for (int i = 0; i < a.length; i++) {
            //可能有相同的数字
            temp[a[i]]++;
        }
        int count = 0;
        for (int j = max; j >= 0; j--) {
            if (count == k) {
                break;
            }
            //可能有相同的所以不用if,用while
            while (temp[j] > 0) {
                count++;
                System.out.println(j);
                temp[j]--;
            }
        }

    }
}

 

 

    原文作者:hanruikai
    原文地址: https://blog.csdn.net/hanruikai/article/details/82494600
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞