首页 > 试题广场 > 查找数组众数
[编程题]查找数组众数
  • 热度指数:3922 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个数组A[n], 定义数组的众数 ( Majority Element) 为数组中出现次数超过 n/2 次的元素, 假设数组A[n]非空且一定存在众数, 请设计算法找到该众数并输出.


输入描述:
一个非空且一定存在众数的整数数组,如: [1,2,2]


输出描述:
输出打印该众数,如: 2
示例1

输入

[1,2,2]

输出

2
示例2

输入

[3,1,-2,3,1,3,3]

输出

3
#include <iostream>
using namespace std;
int main(void){
    int x, mid, time = 1;
    char c;
    cin.get(c);
    cin>>mid;
    while((c = cin.get()) != ']'){
        cin>>x;
        if(mid == x)
            ++time;
        else if(--time == 0)
            time = 1, mid = x;
    }
    cout<<mid<<endl;
    return 0;
}
初始化中位数mid=a[0],出现次数times=1,从第二个数开始遍历数组,a[i]等于mid,次数times加1,否则times减1,再判断减1后times的值,当减1后times变为0时,重新初始化mid=a[i],times=1
发表于 2019-08-16 16:44:04 回复(0)

根据题目中众数的定义,给的数据中一定会出现次数超过n/2的数,那么如果数组中一次删去两个不同的数,那么最后剩下来的数一定是众数,提供一种不用排序,时间复杂度O(n),空间复杂度O(1)的AC方法

import java.util.Scanner;
import static java.lang.System.in;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        String[] str = sc.nextLine().replace("[", "").replace("]", "").split(",");
        int[] data = new int[str.length];
        for (int i = 0; i < data.length; i++) {
            data[i] = Integer.parseInt(str[i]);
        }
        if (data.length == 1 || data.length == 2) {
            System.out.println(data[0]);
            return;
        }
        int hp = 0;
        int flag = data[0];
        for (int i = 0; i < data.length; i++) {
            if (hp == 0) {
                flag = data[i];
                hp++;
            } else if (data[i] == flag) {
                hp++;
            } else{
                hp--;
            }
        }
        System.out.println(flag);
    }
}
编辑于 2019-10-03 21:58:34 回复(2)

也算是取了个巧吧,现将数组排序,然后取排序后数组的中间位置元素就是众数了😂

发表于 2019-03-21 21:39:51 回复(2)
√头像
 
importjava.util.*;
publicclassMain{
    publicintnum(int[] arr){
        Map<Integer,Integer> map = newHashMap<>();
        for(inti = 0; i < arr.length; i++){
            if(map.containsKey(arr[i])){
                map.put(arr[i], map.get(arr[i]) + 1);
            }else{
                map.put(arr[i], 1);
            }
        }
        intmax = 0;
        for(Integer num : map.keySet()){
            if(num > max){
                max = num;
 
            }
        }
        returnmax;
    }
     
}

发表于 2018-12-12 14:52:44 回复(2)
//排序取中间的那个数
import java.io.*;
import java.util.Arrays;
public class Main{
    public static void main(String[] args)throws IOException{
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	String s=br.readLine();
    	String[] str=s.substring(1, s.length()-1).split(",");
    	int[] a=new int[str.length];
    	for(int i=0;i<str.length;i++)
    	    a[i]=Integer.parseInt(str[i]);
    	Arrays.sort(a);
    	System.out.println(a[str.length/2]);
    	    }
}

发表于 2020-05-17 15:07:28 回复(0)
# 由题意可判断出最中间的元素一定就是众数了!排序即可
s = map(int,input().strip('[]').split(','))
s = list(s)
s.sort()
print(s[len(s)//2])

发表于 2020-04-11 23:58:33 回复(0)
JavaScript(Node) 😎题目:有赞👍-Majority Element
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 1){
        let a = inArr[0]
        a = JSON.parse(a)
        a.sort()
        console.log(a[parseInt(a.length/2)])
    }
})


发表于 2020-03-01 17:59:37 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compare(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.second<b.second;
}

int main()
{
    int num;
    vector<int> v;
    while(getchar()!=']')
    {
        cin>>num;
        v.push_back(num);
    }
    sort(v.begin(),v.end());
    vector<pair<int,int>> s;
    int temp=1;
    for(int i=0;i<v.size()-1;i++)
    {
        if(v[i]==v[i+1])
        {
            temp++;
        }
        else
        {
            s.push_back(make_pair(v[i],temp));
            temp=1;
        }
    }
    if(v[v.size()-1]==v[v.size()-2])
        s.push_back(make_pair(v[v.size()-1],temp));
    else
        s.push_back(make_pair(v[v.size()-1],1));
    sort(s.begin(),s.end(),compare);
    auto it=s.end()-1;
    cout<<it->first;
}

发表于 2020-02-18 08:28:00 回复(0)
python2行搞定   评论求一个一行的优雅解法
如果这个众数的数量大于总数的一半   那么排序完后中间位置一定是众数
arr = sorted(eval(input()))
print(arr[len(arr)//2])


发表于 2019-12-30 11:36:25 回复(0)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{
    class Program
    {
        public static void Main(string[] args)
        {
            //string line;
            //while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
            Func(Console.ReadLine());
        }
        //给定一个数组A[n], 定义数组的众数 ( Majority Element) 为数组中出现次数超过 n/2 次的元素, 假设数组A[n]非空且一定存在众数, 请设计算法找到该众数并输出.
        public static void Func(string line)
        {
            var s1 = line.TrimStart('[').TrimEnd(']').Split(',').Select(x => int.Parse(x)).ToArray();
            /*int a = s1.GroupBy(x => x).Select(x => new { val = x.Key, count = x.Count() }).OrderByDescending(x=>x.count).ToArray()[0].val;
            Console.WriteLine(a);*/
            //根据性质 众数数量超过 n/2 也就是说 其他的,每一个数 数量都小于 n/2 所以 每次减一 除了众数其他均会小于0
            int num = 0, count = 0;
            for (int i = 0; i < s1.Length; i++)
            {
                if (s1[i] == num) count++;
                else if (--count < 0)
                {
                    count = 1;
                    num = s1[i];
                }
            }
            Console.WriteLine(num);
        }
    }
}


根据题目定义,真的不得不说是一种非常巧妙的方法!,到最后除了众数能留下来,其他数量小于n/2的均会被替代
发表于 2019-12-10 16:46:07 回复(0)
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] strings = in.nextLine().replace("[","").replace("]","").split(",");
        int[] a = new int[strings.length];
        for (int i=0;i<a.length;i++)
            a[i] = Integer.parseInt(strings[i]);
        int count = 1;
        int data = a[0];
        for (int i=1;i<a.length;i++){
            if (count == 0) {
                data = a[i];count++;
            }else {
                if (a[i] == data)
                    count++;
                else
                    count--;
            }
        }
        System.out.println(data);
    }
}

发表于 2019-08-15 15:40:14 回复(0)
#查找数组中的众数
list = [int(x) for x in input()[1:-1].split(",")]
num = list[0]
n = 1
for i in range(1,len(list)):
    if num != list[i]:
        if n == 0:
            n = 1
            num = list[i]
        else:
            n -= 1
    else:
        n += 1

print(num)
发表于 2019-08-14 11:07:52 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    int l = s.length();
    s = s.substr(1,l-2);
    istringstream ss(s);
    int x;
    char c;
    vector<int> a;
    while(ss>>x){
        a.push_back(x);
        if(ss>>c)
            continue;
    }
    int n = a.size(), cnt = 1;
    x = a[0];
    for(int i=1;i<n;i++){
        if(a[i]==x)
            cnt++;
        else{
            cnt--;
            if(cnt<0){
                x = a[i];
                cnt = 1;
            }
        }
    }
    cout<<x<<endl;
    return 0;
}

发表于 2019-07-15 09:00:56 回复(0)
""""
众数(Majority Element)超过 n/2 次,提供一种O(n)时间复杂度的算法,
本题时间要求不严格可以排序
"""

if __name__ == "__main__":
    a = eval(input().strip())
    cnt = 0
    ans = a[0]
    for x in a:
        if x == ans:
            cnt += 1
        else:
            cnt -= 1
            if cnt < 0:
                ans = x
                cnt = 1
    print(ans)

发表于 2019-07-12 13:02:31 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        String[] strNumber = str.substring(1, str.length() - 1).split(",");
        int[] number = new int[strNumber.length];
        for (int i = 0; i < strNumber.length; i++) {
            number[i] = Integer.parseInt(strNumber[i]);
        }
        Arrays.sort(number);
        System.out.println(number[number.length / 2]);
    }
}
发表于 2019-07-04 17:35:09 回复(0)
#include<bits/stdc++.h> 
using namespace std; 
int main()
{
    vector<int> a;
    string s;
    cin >> s;
    int cur, sign = 1;
    for (int i = 1; i < s.length(); i++)
    {
        if (!isdigit(s[i]) && s[i] != '-')
        {
            a.push_back(cur * sign);
            cur = 0;
            sign = 1;
        }
        else if (isdigit(s[i]))
            cur = cur * 10 + s[i] - '0';
        else
            sign = -1;
    }
    if(a.size()==1)
        cout<<a[0];
    sort(a.begin(),a.end());
    int n=1;
    for(int i=1;i<a.size();i++)
    {
        if(a[i]==a[i-1])
        {
            n++;
            if(n>a.size()/2)
            {
                cout<<a[i];
                break;
            }
        }
        else
            n=1;
    }
    return 0;
}

发表于 2019-07-03 15:16:26 回复(0)
public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String str = s.next();
        String[] split = str.substring(1, str.length() - 1).split(",");
        int max = 0;
        int res = 0;
        for (int i = 0; i < split.length; i++) {
            int num = 0;
            for (int i1 = 0; i1 < split.length; i1++) {
                if(Integer.parseInt(split[i]) == Integer.parseInt(split[i1])){
                    num++;
                }
            }
            if(num > max){
                max = num;
                res = Integer.parseInt(split[i]);
            }
        }
        System.out.println(res);
    }
发表于 2020-05-11 21:53:21 回复(0)
#include<iostream>
(720)#include<vector>
#include<algorithm>

using namespace std;

int main(void){
    char c;
    int num;
    cin>>c;
    cin>>num>>c;
    int t = 0;
    int ans = 0;
    if (c == ']'){
        cout<<num<<endl;
        return 0;
    }
    while (c != ']'){
        if (t == 0){
            t++;
            ans = num;
        }
        else if(num == ans){
            t++;
        }
        else if(num != ans){
            t--;
        }
        cin>>num>>c;
    }
    if (t == 0)
        ans = num;
    cout<<ans<<endl;
    return 0;
}

发表于 2020-05-10 16:51:47 回复(0)
投票法
import sys


if __name__ == "__main__":
    #sys.stdin = open("input", "r")
    A = input()[1:-1]
    A = list(map(int, A.split(",")))
    result = A[0]
    count = 1
    for i in range(1, len(A)):
        if result == A[i]:
            count += 1
        else:
            count -= 1
        if count == 0:
            result = A[i+1]
    print(result)





发表于 2020-04-08 15:37:50 回复(0)
nums=list(map(int,input().strip('[|]').split(',')));
p={};
ma=0;
l=len(nums)//2
for i in nums:
    p[i]=p.get(i,0)+1;
    if p[i]>l:
        print(i);
        break;

发表于 2020-04-03 11:25:48 回复(0)