数组中最大的k个数

[编程题]数组中最大的k个数

热度指数：120 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

求取一个数组最大K个数，返回k个数可以为任意排序，假设数组元素有N个，要求算法时间复杂度不大于O(N*log（K)），空间复杂度为O(1)。

示例1

输入

[3, 2, 1, 4, 5],2

输出

[5,4]

备注:

输出结果从大到小排列

算法知识视频讲解

pein531

无视复杂度的要求，直接利用插入排序或堆排序的思想求解topk😂

import java.util.Arrays;
import java.util.Comparator;


public class Solution {
    /**
     * 
     * @param li int整型一维数组 
     * @param k int整型 
     * @return int整型一维数组
     */
    public int[] top_k (int[] li, int k) {
        // write code here
        int n = li.length;
        // 用插入排序的思想
        int[] temp = Arrays.copyOfRange(li, 0, k);
        Arrays.sort(temp);
        reverse(temp);
        for(int i = k; i < n; i++){
            if(li[i] > temp[temp.length - 1])
                temp[temp.length - 1] = li[i];
            Arrays.sort(temp);
            reverse(temp);
        }
        return temp;
    }
    
    private static void reverse(int[] arr) {
        for(int i = 0; i < arr.length / 2; i++){
            int temp = arr[i];
            arr[i] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
        }
    }
}

发表于 2021-02-07 10:35:13 回复(0)

侬是一个好人

void Swap(int& x,int& y)
{
int tmp = x;
x = y;
y = tmp;
}
//向下调整(小堆)
void AdjustDown(vector<int>& a,int n,int parent) //注意这里vector<int>& 要用引用
{
int child = 2 * parent + 1;
while(child < n)
{
if(child+1 < n && a[child] > a[child+1])
child++;
if(a[child] < a[parent])
{
Swap(a[child],a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
break;
}
}
vector<int> top_k(int* li, int liLen, int k) {
vector<int> retArr;
retArr.resize(k);
for(int i = 0; i < k; i++)
retArr[i] = li[i];
//用数组的前k个数建小堆
for(int i = (k-1-1)/2; i >= 0; i--)
AdjustDown(retArr,k,i);
//剩下的liLen-k个数一次与堆顶的数据比较
for(int j = k; j < liLen; j++)
{
if(li[j] > retArr[0])
{
retArr[0] = li[j]; //若大于堆顶数据,则替换
}
//进行一次向下调整
AdjustDown(retArr,k,0);
}
//得到的k个数就是最大的k个数,且保证了空间复杂度为O(k)
//得注意输出的顺序,最大的K个数按照从大到小的顺序输出
reverse(retArr.begin(),retArr.end());
return retArr;
}
};

发表于 2022-10-15 21:23:22 回复(0)

Java

菲尼克斯弗兰克

import java.util.*;
public class Solution {
// 找前k个大的数-堆排序
    public int[] top_k (int[] arr, int k) {
        int end = arr.length-1;
        for (int i = end/2; i >= 0; i--) { // 先建堆
            adjust(arr, i, end);
        }
        for (int i = 0; i < k; i++) { // 先交换再调整k次
            swap(arr, 0, end);
            adjust(arr, 0, --end);
        }
        int[] res = new int[k];
        int idx = 0;
        for (int i = 0; i < k; i++) {
            res[idx++] = arr[arr.length-1-i];
        }
        return res;
    }
    // 调整函数
    public void adjust(int[] arr, int idx, int end) {
        int imax = idx;
        int l = idx * 2 + 1, r = l+1;
        if (l <= end && arr[l] > arr[imax]) imax = l;
        if (r <= end && arr[r] > arr[imax]) imax = r;
        if (imax == idx) return;
        else { // 可以交换继续换
            swap(arr, imax, idx);
            idx = imax;
            adjust(arr, idx, end);
        }
    }
    // 辅助交换
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

发表于 2022-07-19 15:10:17 回复(0)