用贪心算法求解一个问题
本帖最后由 yabanbingliang 于 2020-6-1 10:14 编辑请使用贪心算法解决下列问题
求解一个序列中出现次数最多的元素
【问题描述】给定n个正整数，编写程序找出它们中出现次数最多的数，如果这样的数有多个，输出其中最小的数。
有没有大佬！帮俺康康{:10_266:}
这本来是个O(n)的问题，用词典：整数值：次数。。。就行了
非得贪心算法，真是个难题，不知道怎么贪心，一般贪心是针对o(n的n次方) 本帖最后由 Darth_EF 于 2020-6-1 12:47 编辑
// javascript
var n=233; // n
var arr=new Array(n);
for(var i=n-1;i>=0;--i){ //用随机数填充数组内容
arr=Math.floor(Math.random()*10);
}
var _v_s=[];
for(var i=n-1;i>=0;--i){ //记录某数字出现的次数
var j;
for(j=_v_s.length-1;j>=0;--j){
if(_v_s.value==arr){
_v_s.sum+=1;
break;
}
}
if(j==-1)_v_s.push({value:arr,sum:1});
}
tempValue=v_s;
for(var i=v_s.length-2;i>=0;--i){
if(tempValue.sum<v_s.sum){
tempValue=v_s;
}else{
if(tempValue.sum==v_s.sum.value>v_s.value){tempValue=v_s;}
}
}
console.log(v_s);
console.log(tempValue);
很菜，不知道贪心算法怎么写;由于我这里没装c的环境所以是用js写的，换成c也差不多。支持楼上 java2python 发表于 2020-6-1 11:10
这本来是个O(n)的问题，用词典：整数值：次数。。。就行了
非得贪心算法，真是个难题，不知道怎么贪心，一 ...
我也不想用贪心啊{:10_266:}可这是实验的题目{:10_266:} Darth_EF 发表于 2020-6-1 11:44
很菜，不知道贪心算法怎么写;由于我这里没装c的环境所以是用js写的，换成c也差不多。支持楼上
谢谢你{:5_109:}我研究研究 本帖最后由 赚小钱 于 2020-6-1 15:37 编辑
去学一下数据结构: 堆
使用数据结构
struct Elem {
int value;
int times;
}
作为元素，构建一个最大堆。算法满足贪心算法的思想。时间复杂度为 O(n)。 首先感谢，让我又看到个新名词：贪心算法！去查了下资料，对于它的讲解。个人感觉和遍历，穷举没什么区别 i dont know that whether i didis greedy algorithm ，but maybe it can dislove your problem
#include<iostream>
#include<cstdio>
using namespace std;
int func(int a[],int n,int hash[],int &i,int &imax){
if(n==1){
imax=0;
i=a;
hash]=1;
return 1;
}else{
int k=-1;
k=func(a,n-1,hash,i,imax);
++hash];//把当前的值压入哈希，判断上一层传递过来的次数与当前次数比较
if(hash]>k){//当前层大于上一层的最多次数 ，更新imax，返回次数
imax=n-1;
return hash];
}else if(hash==k]){//次数一样时
if(a<a){
imax=n-1;//更新
return hash];//返回最多次数
}
}
}
}
int main(){
int n=6,i=-1,imax=-1;
int hash={0};
int a={1,2,2,2,1,1};
func(a,6,hash,i,imax);
cout<<a<<endl;
}
页:
[1]