精华内容
下载资源
问答
  • N数组 topK问题 解法

    2020-12-03 23:35:05
    有N个长度不一的数组,所有的数组都是有序的,请从大到小打印这N个数组整体最大的前K个数。 例如,输入含有N行元素的二维数组可以代表N个一维数组。 219, 405, 538, 845, 971 148, 558 52, 99, 348, 691 再输入整数k...

    题目描述
    有N个长度不一的数组,所有的数组都是有序的,请从大到小打印这N个数组整体最大的前K个数。
    例如,输入含有N行元素的二维数组可以代表N个一维数组。
    219, 405, 538, 845, 971
    148, 558
    52, 99, 348, 691
    再输入整数k=5,则打印:
    Top 5: 971, 845, 691, 558, 538
    [要求]
    时间复杂度为O(k \log k)O(klogk),空间复杂度为O(k \log k)O(klogk)

    C++优先队列是优先级高的在队首,定义优先级大小的方式是传入一个算子的参数比较a, b两个东西,返回true则a的优先级<b的优先级。

    默认是less算子也就是返回a<b,也就是小的优先级也小,而greater算子返回a>b,小的优先级高。

    如果是默认的less算子,值大的优先级高,值大的排到了队头,优先队列大的先出队。

    
    #include<iostream>
    #include <bits/stdc++.h>
    #include<vector>
    #include<queue>
    using namespace std;
    
    int main(void) {
        priority_queue<int,vector<int>,greater<int> >q;
        // t 个 数组,前 k 个最大元素
        int t,k,n,x; cin>> t>>k;
        
        for (int i=0;i<t;++i) {
            cin>>n;
            while (n--) {
                scanf("%d", &x);
                if (n<=k) q.push(x);
                if(q.size() >k) q.pop();
            }
        }
        int res[k];
        for (int i= k-1; i>=0;--i) {
            res[i] = q.top(),q.pop();
        }
        for (int i=0;i<k;++i) printf("%d ", res[i]);
        printf("\n");
        
        
    }
    
    
    展开全文
  • TOP K即返回给定集合最大的K个元素,这个集合有可能很大,十亿,有可能万亿,所以对算法的要求比较高。以下是我的总结: ...同理我们也可以使用该思想求数组TOP K。也是使用第一个元素左右标志,小于该点的元

    TOP K即返回给定集合最大的K个元素,这个集合有可能很大,十亿,有可能万亿,所以对算法的要求比较高。以下是我的总结:

    一、采用快速排序的分治算法思想进行求解:

    快速排序的思想是使用一个标志点将数组分为两个部分,小于该点的数据移动到该点的左侧,大于该点的数据移动到该点的右侧,然后进行递归,最后达到有序。同理我们也可以使用该思想求数组的TOP K。也是使用第一个元素左右标志,小于该点的元素移到左侧,大于该点的元素移到右侧,第一次partition后有有三种情况:

    1、标志点右侧的数据正好是K-1,那么加上标志点就是要求的TOP K个元素

    2、标志点右侧的数据个数N小于K-1,那么就需要在标志点左侧的集合中寻找TOP (K- N),通过递归就可以实现

    3、标志点右侧的数据个数N大于K-1,那么就需要在标志点右侧的集合中需要TOP K个元素,通过递归实现

    代码如下:

    #include <stdio.h>
    #include <unistd.h>
    
    void getRand(int* data, int length) {
        int i;
        srand((unsigned int) getpid());
        for (i = 0; i < length; i++) {
            data[i] = rand() % 1000;
        }
        //print the array
        printf("generate the array using rand:\n");
        for (i = 0; i < length; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
    }
    
    void partition(int arr[], int low, int high, int *pos){
            int key = arr[low];
            int i = low, j = high;
            while(i < j){
                    while(i < j && arr[j] > key) j--;
                    if(i < j){
                            arr[i++] = arr[j];
                    }
                    while(i < j && arr[i] < key) i++;
                    if(i < j){
                            arr[j--] = arr[i];
                    }
                    //arr[i] = key;
            }
            arr[i] = key;
            *pos = i;
    }
    
    int topK(int arr[], int low, int high, int k){
            int pos =0;
            partition(arr, low, high, &pos);
            int num = high - pos + 1;
            int index = -1;
            if(num == k){
                    index = pos;
            }else if(num > k){
                    index = topK(arr, pos + 1, high, k);
            }else{
                    index =  topK(arr, low, pos -1, k - num);
            }
            return index;
    }
    
    int main(){
            int arr[10] = {0};
            getRand(arr, 10);
            int pos;
            pos = topK(arr, 0, 9, 5);
            for(;pos < 10;pos++){
                    printf("%d\t", arr[pos]);
            }
            printf("\n");
    }

    这种算法的缺点是需要针对数据做频繁的移动操作,如果数据量较大就需要使用文件的形式进行分治计算。

    二、使用最小堆取得TOP K元素是一种很好的方式

    至于为为什么使用最小堆,那是因为最小堆堆顶是最小的元素,只有大于堆顶的元素才会加入堆,然后对堆进行adjust。这种方式只需要维护K个元素的 最小堆。

    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    
    void print(int arr[], int size){
            int i = 0;
            for(; i < size;i++){
                    printf("%d\t", arr[i]);
            }
    }
    //最小堆是排序的
    void add(int arr[],int size,int num){
            if(num > arr[0]){
                    arr[0] = num;
                    //调整堆
                    int i = 0;
                    for(;i < size -1 && num > arr[i+1];i++){
                            arr[i] = arr[i+1];
                    }
                    arr[i] = num;
            }
    }
    //最小堆不排序(开始元素是1)
    void sink(int arr[], int size, int num){
            if(num > arr[1]){
                    arr[1] = num;
                    int i = 1;
                    while(2 * i <= size){
                            int j = 2 * i;
                            if(j < size && arr[j + 1] < arr[j]) j++;
                            if(arr[i] > arr[j]){
                                    int tmp = arr[i];
                                    arr[i] = arr[j];
                                    arr[j] = tmp;
                                    i = j;
                            }else{
                                    break;
                            }
                    }
            }
    }
    
    void getRand(int* data, int length) {
        int i;
        srand((unsigned int) getpid());
        for (i = 0; i < length; i++) {
            data[i] = rand() % 1000;
        }
        //print the array
        printf("generate the array using rand:\n");
        for (i = 0; i < length; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
    }
    
    int main(int argc, char *argv[]){
            int arr[11] = {0};
            int heap[10] = {0};
            int heap2[11] = {0};
            getRand(arr, 11);
            int i;
            for(;i< 11;i++){
                    add(heap, 10, arr[i]);
                    sink(heap2, 10, arr[i]);
    
            }
            print(heap, 10);
            int j = 1;
            for(; j < 11;j++){
                    printf("%d\t", heap2[j]);
            }
    }
    展开全文
  • 算法-求数组topK的递增子数组 上一篇讲的是top2的子数组,这一篇讲一下topK的子数组,使用动态规划实现,本方法是大佬在评论区给出的 点击这里 核心代码不变,我做了一点小小的改动。 dp[i]表示为到i的最长子数组...

    算法-求数组中topK的递增子数组

    上一篇讲的是top2的子数组,这一篇讲一下topK的子数组,使用动态规划实现,本方法是大佬在评论区给出的 点击这里 核心代码不变,我做了一点小小的改动。

    dp[i]表示为到i的最长子数组长度

        public static void main(String[] args) {
            System.out.println(topKArray(new int[]{2, 1, 4, 5, 8, 3, 7, 10, 11,12, 5},2));
        }
        public static List<List<Integer>> topKArray(int nums[],int k){
            if(k==0){
                return new ArrayList<>();
            }
            int dp[]=new int[nums.length];//dp[i]表示到i的最大上升子序列长度
            for(int i=0;i<dp.length;i++){
                dp[i]=1;//为啥是1呢,因为至少自己也是一个子序列
            }
            for (int i=1;i<nums.length;i++){
                if(nums[i]>nums[i-1]){
                    dp[i]=dp[i-1]+1;
                }
            }
            List<List<Integer>> res=new LinkedList<>();
            while (k-->0){
                int curMax=dp[0];
                int currMaxPos=0;
                for (int i=0;i<dp.length;i++){
                    if(dp[i]>curMax){
                        curMax=dp[i];
                        currMaxPos=i;
                    }
                }
                List<Integer> list=new LinkedList<>();
                while (curMax-->0){
                    list.add(0,nums[currMaxPos]);
                    dp[currMaxPos]=1;//消除这一段
                    currMaxPos--;
                }
                res.add(list);
            }
            return res;
        }
    
    展开全文
  • N个有序数组TOPK问题 假设K个N元素的有序数组,求解最小的TOPK问题的C语言实现 //求解N个元素的大小的K个数组里面的TOPK小元素 #include <iostream> using namespace std; #define K 3 #define N 4 #define...

    N个长度不一的有序数组的TOPK问题

    假设K个长度不一的有序数组,求解TOPK最小元素 问题的C++语言实现

    总结:
    可以查阅左程云算法书第八章TOPK问题(java),本文章属于自写,细节可能写的不多,但是基本思想和其是一致的。

    1. 基本上在熟悉堆排序源代码的基础之上,只要把以前只存在数值的堆节点变成结构体堆节点,其他逻辑都是一样的。
    2. 结构体节点:当前节点的数值大小,当前节点数值在二维数组中的行号,当前节点元素的所在行的下一个元素的列下标。
    • 提取K个数组中每一个数组的第一个元素,建立K大小的最小堆(从最后一个非叶子节点开始调整)。

    • 弹出堆顶元素并存放在新数组中,并将堆顶元素所在二维数组对应行,下一列元素放入堆顶,针对堆顶进行最小堆调整。

    • 执行TOPK次,就是TOPK个最小元素

    tip:通过利用vector的size()函数可以有效控制判断数组是否到达行数组的末尾。

    设计到结构体的这种,最好写一个swap函数进行交换。

    时间复杂性:建立堆O(K)+重建堆O(NKlogK)=O(NKlogK)

    空间复杂性O(1)

    #include <iostream>
    #include <vector>
    using namespace std;
    
    #define K 3
    #define MaxValue SHRT_MAX
    
    //堆节点定义
    struct Node
    {
    	short value;//数组的当前元素对应值大小
    	short arrnum;//数组索引
    	short index;//数组的当前元素下一个元素的索引
    };
    
    //最小堆数组
    Node MinHeap[K];
    
    //交换元素
    void Swap(Node &X, Node &Y)
    {
    	Node temp = X;
    	X = Y;
    	Y = temp;
    }
    
    //针对K个元素,以i节点的向下过滤函数
    void PerDown(Node A[], const char i, const char N)
    {
    	Node temp = A[i];
    
    	char Parent, Child;
    	for (Parent = i; Parent * 2 + 1 < N; Parent = Child)
    	{
    		Child = Parent * 2 + 1;
    		if (Child+1 < N && A[Child+1].value < A[Child].value)
    		{
    			Child++;
    		}
    
    		if (temp.value <= A[Child].value)
    		{
    			break;
    		}
    		else
    		{
    			swap(A[Parent], A[Child]);
    		}
    	}
    	A[Parent].arrnum = temp.arrnum;
    	A[Parent].index = temp.index;
    	A[Parent].value = temp.value;
    }
    
    //创建最小堆
    void BuildMinHeap()
    {
    	for (char i = (K - 1) / 2; i >= 0; i--)
    	{
    		PerDown(MinHeap, i, K);
    	}
    }
    
    
    void TopK(const vector<vector<short>> &InArray, vector<short> &OutArray, const short &TOPK)
    {
    	//创建K大小的数组
    	for (char i = 0; i < K; i++)
    	{
    		MinHeap[i].value = InArray[i][0];
    		MinHeap[i].arrnum = i;
    		MinHeap[i].index = 1;
    	}
    
    	//针对数组做最小堆处理
    	BuildMinHeap();
    
    	for (char i = 0; i < TOPK; i++)
    	{
    		//先取节点出来
    		Node temp = MinHeap[0];
    		//把节点的值取出来
    		OutArray.push_back(temp.value);
    
    		//数组索引无需修改,数组元素索引+1
    		if (temp.index < InArray[temp.arrnum].size())
    		{
    			MinHeap[0].value = InArray[temp.arrnum][temp.index];
    			MinHeap[0].index++;
    		}
    		else//溢出处理
    		{
    			MinHeap[0].value = MaxValue;
    		}
    		
    		PerDown(MinHeap, 0, K);
    	}
    }
    
    void main()
    {
    	short TOPK = 15;
    	//最终存放TOPK个最小元素的容器
    	vector <short> OutArray;
    	//K个原始数组
    	short arr1[3] = { 56,78,981 };
    	short arr2[4] = { 24,89,901,1003 };
    	short arr3[6] = { 35,47,79,103,256,345 };
    	//转为一维向量
    	vector<short> InArray1(arr1, arr1 + sizeof(arr1) / sizeof(short));
    	vector<short> InArray2(arr2, arr2 + sizeof(arr2) / sizeof(short));
    	vector<short> InArray3(arr3, arr3 + sizeof(arr3) / sizeof(short));
    	//总元素个数以及TOPK的确定
    	short total = InArray1.size() + InArray2.size() + InArray3.size();
    	TOPK = TOPK > total ? total : TOPK;
    	//转为二维向量
    	vector<vector<short>> InArray;
    	InArray.push_back(InArray1);
    	InArray.push_back(InArray2);
    	InArray.push_back(InArray3);
    
    	//求解TOPK
    	TopK(InArray, OutArray, TOPK);
    	//打印输出
    	for (char i = 0; i < TOPK; i++)
    	{
    		cout << OutArray[i] << endl;
    	}
    
    	system("pause");
    }
    
    
    展开全文
  • 思路:利用快排在排序时,把数组分成...如果i大于K,那么说明第K大值在数组左边,则继续在左边查找;如果i小于K,那么说明第K大值在数组的右边,继续在右边查找;每一轮排序都重复上述步骤,直到找到第K大值。 import j
  • 单调旋转数组TopK问题
  • 数组topK

    2019-03-29 15:55:45
    package com.sitech.iot.monitor.controller; import java.util.PriorityQueue; public class demo { public static int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minQueu...
  • Given a non-empty array of integers, return thekmost frequent elements. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Note...
  • 1、第一种代码 ,默认是浮点型的topk,如果需要切换成整形数组topk,应注意把代码所有地方的float 类型改成 float 由于c语言对类型转换非常敏感,整形转浮点型可能会导致精度损失,比如float类型的 0.3333 直接赋值...
  • 这个问题大致是说,如何在给定的两个有序数组里面找其中的中值,或者变形问题,如何在2个有序数组数组中查找Top K的值(Top K的问题可以转换成求第k个元素的问题)。这个算法在很多实际应用中都会用到,特别是在当前...
  • topk数组中的k项最大值//二维数组中的k项最大值暴力解法快排解法堆排解法堆排获取包含n堆数组的前k项 暴力解法 这个基本思路类似于冒泡排序或者插入排序,以此遍历找到最大的数,最后返回k个最大的数,时间复杂度...
  • * 寻找Top k 大 * * @param nums * @param k * @return */ public static int findKthLargest(int[] nums, int k) { return findKthLargest(nums, k, 0, nums.length - 1); } // 快速排序-选择的内部实现...
  • 题目描述 在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4...
  • 面试:数组Topk _1

    2016-05-14 23:50:28
    求一维数组中最小的k个数字 算法_1:快排算法 复杂度:O(klgn) import java.util.*;class Solution{ //选择一个数,将数组分为大小两个部分 public int partition(int data[],int start,int end){ int pivot...
  • numpy高维数组获取top-K

    2021-01-12 14:41:10
    文章目录前言正文后记 前言 理论知识请自行翻阅numpy的argpartition和partition方法的实现原理,该文章仅仅包含...def get_sorted_top_k(array, top_k=1, axis=-1, reverse=False): """ 多维数组排序 Args: arra
  • 打印N个数组中的TopK

    2018-11-11 14:43:13
    描述:有N个长度不一样的数组,每个数组都是有序的,找出这个N个数组TopK 要求: 如果所有数组的元素个数之和小于k,则从大到小打印所有的数 时间复杂度为 解答:利用堆结构和堆排序的过程完成 构建一个大小为N...
  • 数组TopK的三种解决方法---Java

    千次阅读 2019-06-19 15:20:27
    此种方法就不多做解释了,就是使用快排,归并,堆排序等方法先将数组完全排序,然后再取topK,时间复杂度为O(NlogN)。而且这种方法不适用于大数据量,小内存。 方法二:快排思想,部分排序 此种方法时借鉴快排的...
  • } 时间复杂度和应用场景 时间复杂度:O(nlogn) 应用场景: 巨大的数据流总的各种topK问题 优先队列 利用堆排序实现的N个数组topK N个长短不一的有序数组,找出所有数组元素里面的topK。 主要思路 每次都对每个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,098
精华内容 439
关键字:

数组topk