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

yabanbingliang

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

有没有大佬！帮俺康康

最佳答案

月排行榜 / 总排行榜

Darth_EF

2020-6-1 11:44:50

// javascript
        var n=233;                  // n
        var arr=new Array(n);   
        for(var i=n-1;i>=0;--i){   //用随机数填充数组内容
            arr[i]=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[j].value==arr[i]){
                    _v_s[j].sum+=1;
                    break;
                }
            }
            if(j==-1)_v_s.push({value:arr[i],sum:1});
        }

        tempValue=v_s[v_s.length-1];
        for(var i=v_s.length-2;i>=0;--i){
            if(tempValue.sum<v_s[i].sum){
                tempValue=v_s[i];
            }else{
                if(tempValue.sum==v_s[i].sum.value>v_s[i].value){tempValue=v_s[i];}
            }
        }
        console.log(v_s);
        console.log(tempValue);

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

跳转到最佳答案楼层

java2python

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

Darth_EF

// javascript
        var n=233;                  // n
        var arr=new Array(n);   
        for(var i=n-1;i>=0;--i){   //用随机数填充数组内容
            arr[i]=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[j].value==arr[i]){
                    _v_s[j].sum+=1;
                    break;
                }
            }
            if(j==-1)_v_s.push({value:arr[i],sum:1});
        }

        tempValue=v_s[v_s.length-1];
        for(var i=v_s.length-2;i>=0;--i){
            if(tempValue.sum<v_s[i].sum){
                tempValue=v_s[i];
            }else{
                if(tempValue.sum==v_s[i].sum.value>v_s[i].value){tempValue=v_s[i];}
            }
        }
        console.log(v_s);
        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也差不多。支持楼上

谢谢你我研究研究

赚小钱

去学一下数据结构: 堆

使用数据结构

struct Elem {
    int value;
    int times;
}

作为元素，构建一个最大堆。算法满足贪心算法的思想。时间复杂度为 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;
}