[已解决]用贪心算法求解一个问题

yabanbingliang

请使用贪心算法解决下列问题
求解一个序列中出现次数最多的元素
【问题描述】给定n个正整数，编写程序找出它们中出现次数最多的数，如果这样的数有多个，输出其中最小的数。

有没有大佬！帮俺康康

最佳答案

月排行榜 / 总排行榜

Darth_EF

2020-6-1 11:44:50

1. // javascript
   
2.         var n=233;                  // n
   
3.         var arr=new Array(n);   
   
4.         for(var i=n-1;i>=0;--i){   //用随机数填充数组内容
   
5.             arr[i]=Math.floor(Math.random()*10);
   
6.         }
   
7. 
   
8.         var _v_s=[];
   
9.         for(var i=n-1;i>=0;--i){    //记录某数字出现的次数
   
10.             var j;
    
11.             for(j=_v_s.length-1;j>=0;--j){
    
12.                 if(_v_s[j].value==arr[i]){
    
13.                     _v_s[j].sum+=1;
    
14.                     break;
    
15.                 }
    
16.             }
    
17.             if(j==-1)_v_s.push({value:arr[i],sum:1});
    
18.         }
    
19. 
    
20.         tempValue=v_s[v_s.length-1];
    
21.         for(var i=v_s.length-2;i>=0;--i){
    
22.             if(tempValue.sum<v_s[i].sum){
    
23.                 tempValue=v_s[i];
    
24.             }else{
    
25.                 if(tempValue.sum==v_s[i].sum.value>v_s[i].value){tempValue=v_s[i];}
    
26.             }
    
27.         }
    
28.         console.log(v_s);
    
29.         console.log(tempValue);

复制代码

很菜，不知道贪心算法怎么写;由于我这里没装c的环境所以是用js写的，换成c也差不多。支持楼上

跳转到最佳答案楼层

java2python

这本来是个O(n)的问题，用词典：整数值：次数。。。就行了
非得贪心算法，真是个难题，不知道怎么贪心，一般贪心是针对o(n的n次方)

Darth_EF

1. // javascript
   
2.         var n=233;                  // n
   
3.         var arr=new Array(n);   
   
4.         for(var i=n-1;i>=0;--i){   //用随机数填充数组内容
   
5.             arr[i]=Math.floor(Math.random()*10);
   
6.         }
   
7. 
   
8.         var _v_s=[];
   
9.         for(var i=n-1;i>=0;--i){    //记录某数字出现的次数
   
10.             var j;
    
11.             for(j=_v_s.length-1;j>=0;--j){
    
12.                 if(_v_s[j].value==arr[i]){
    
13.                     _v_s[j].sum+=1;
    
14.                     break;
    
15.                 }
    
16.             }
    
17.             if(j==-1)_v_s.push({value:arr[i],sum:1});
    
18.         }
    
19. 
    
20.         tempValue=v_s[v_s.length-1];
    
21.         for(var i=v_s.length-2;i>=0;--i){
    
22.             if(tempValue.sum<v_s[i].sum){
    
23.                 tempValue=v_s[i];
    
24.             }else{
    
25.                 if(tempValue.sum==v_s[i].sum.value>v_s[i].value){tempValue=v_s[i];}
    
26.             }
    
27.         }
    
28.         console.log(v_s);
    
29.         console.log(tempValue);

复制代码

很菜，不知道贪心算法怎么写;由于我这里没装c的环境所以是用js写的，换成c也差不多。支持楼上

yabanbingliang

java2python 发表于 2020-6-1 11:10
这本来是个O(n)的问题，用词典：整数值：次数。。。就行了
非得贪心算法，真是个难题，不知道怎么贪心，一 ...

我也不想用贪心啊可这是实验的题目

yabanbingliang

Darth_EF 发表于 2020-6-1 11:44
很菜，不知道贪心算法怎么写;由于我这里没装c的环境所以是用js写的，换成c也差不多。支持楼上

谢谢你我研究研究

赚小钱

去学一下数据结构: 堆

使用数据结构

1. struct Elem {
   
2.     int value;
   
3.     int times;
   
4. }

复制代码

作为元素，构建一个最大堆。算法满足贪心算法的思想。时间复杂度为 O(n)。

405794672

首先感谢，让我又看到个新名词：贪心算法！去查了下资料，对于它的讲解。个人感觉和遍历，穷举没什么区别

soupman

i dont know that whether i did  is 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[0];
        hash[a[0]]=1;
        return 1;
    }else{
         int k=-1;
         k=func(a,n-1,hash,i,imax);
         ++hash[a[n-1]];//把当前的值压入哈希，判断上一层传递过来的次数与当前次数比较
         if(hash[a[n-1]]>k){//当前层大于上一层的最多次数 ，更新imax，返回次数
             imax=n-1;
            return hash[a[n-1]];
         }else if(hash[a[n-1]==k]){//次数一样时
              if(a[n-1]<a[imax]){
                  imax=n-1;//更新
                return hash[a[n-1]];//返回最多次数
              }
         }
    }
}
int main(){
    int n=6,i=-1,imax=-1;
    int hash[6]={0};
    int a[6]={1,2,2,2,1,1};
    func(a,6,hash,i,imax);
    cout<<a[imax]<<endl;
}