【你问我答】N个数组选择K个,如何使这K个数组公共元素最多?

问题描述:

N个数组,选择K个,如何选择可以使这K个数组的公共元素最多?

回答有奖:

选取一位认真回答问题的牛友,赠送200牛币!
▶回答尽量有自己的思考,不要单纯的只是复制粘贴定理定义,或者他人blog哦~

你问我答问题汇总:点击进入

------------
#我也有问题想询问牛友,怎么办?

欢迎私信@筱茜 说明你的问题,将根据问题具体情况排期进入【你问我答】专场~
私信请注明参与【你问我答】专场哦~

你问我答 - 答问题,成大佬,拿牛币!
你问我答是牛客新栏目,每周1期几个问题,
牛友在问题贴下留下自己的知识,经验与见解,
帮助更多牛友了解更多技术相关知识!
#悬赏#
全部评论
采用缩小样本法: x={x1,x2,x3……xn} y={y1,y2,y3……yn} z={z1,z2,z3……zn} 根据题意如何选择其中两个,使得两个数组公共元素最多。 遍历 x、y、z三个数组的每个元素 任选其中一个数组分别与另外两个数组做元素比较 如果相同,则记录count++ count最大的为数组公共元素最多的 for(i=0;i<x.length;i++){     for(j=0;j<y.length;y++){         if(x[i]==y[j]){             count++;   //count初始值为0,作为记录统计         }     } }
点赞 回复
分享
发布于 2019-08-07 06:18
1. 遍历N个数组,得到每个数字在N个数组出现的情况。可以用hash table存储,key为数字,value为自定义类型。 2. 根据mappedCount对key排序,同时剔除掉mappedCount < K的key,用mappingInfo *sortedMapping指针数组存储就好 3. 从mappedCount最小的key开始枚举遍历sortedMapping,同时把结果存储hash table,key为uint32 *mapping转出的字符串,value为匹配的数字个数。这里用hash table存储是避免重复计算,用转出的字符串做key是为了查找方便,如果你愿意自定义查找函数,用uint32 *mapping做key更快 4. 遍历hash table,找到count最大的,而key的含义就能得到是哪几个数组。 空间复杂度O(M) 时间复杂度O(M*lgM) M=count(key) 代码如下: class Solution {     public int findKthLargest(int[] nums, int k) {         Arrays.sort(nums);         if(nums.length==0) return 0;         int i=nums.length-1;         int result=0;         while(k>0){                         i--;             k--;         }                 return nums[i+1];     } }
点赞 回复
分享
发布于 2019-08-06 13:00
春招专场
校招火热招聘中
官网直投

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务