首页 > 试题广场 >

查找数组众数

[编程题]查找数组众数
  • 热度指数:5389 时间限制: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

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

发表于 2019-03-21 21:39:51 回复(4)
#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)
√头像
 
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)
lst = input().replace("[","").replace("]","").replace(","," ").split()
#print(len(lst))
#print(int(9/2))#向下取整
l = []
for i in lst:
    if lst.count(i) > int(len(lst)/2):
        l.append(i)
ll = list(set(l))
print(''.join(ll))
暴力做法
发表于 2022-05-11 15:03:01 回复(0)
//排序取中间的那个数
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)
package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var s string
    fmt.Fscan(in,&s)
    s=s[1:len(s)-1]
    sarr:=strings.Split(s,",")
    cnt:=map[string]int{}
    for _,s:=range sarr{
        cnt[s]++
        if cnt[s]*2>len(sarr){
            fmt.Print(s)
            break
        }
    }
}

发表于 2023-03-21 22:36:01 回复(0)
import java.util.Scanner;
/**
 * 投票法求众数
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] nums = new int[64];

        // 获取数组
        String s = in.nextLine();
        String[] strs = s.replaceAll("[\\[\\]]","").split(",");
        int k=0;
        for(int i=0;i<strs.length;i++){
            nums[k++] = Integer.valueOf(strs[i]);
        }

        // 投票
        int count = 0;
        int candidate = 0;
        for(int i=0;i<k;i++){
            if(count == 0){
                candidate = nums[i];
            }
            count += candidate == nums[i]?1:-1;
        }
        System.out.println(candidate);
    }
}

发表于 2023-03-08 15:28:11 回复(0)
都是坑 给我恶心坏了
#include <stdio.h>
#include <string.h>
void swap(int *str,int len)
{
    for(int i = 0;i<len-1;i++)
    {
        for(int j = 0;j<len-i-1;j++)
        {
            if(str[j]>str[j+1])
            {
                int temp= str[j];
                str[j]=str[j+1];
                str[j+1]=temp;
            }
        }
    }
}

int StoT(char *str)
{
    int NB=0;
    int WC=0;
    int Number=0;
    for(int i = strlen(str)-1;i>=0;i--)
    {
        if(str[i]!='0'&&i!=strlen(str)-1&&str[0]!='-')
        {
         Number+=((str[i]-48)*pow(10,++NB));
        }
        else if(str[i]=='0'&&i!=strlen(str)-1&&str[0]!='-')
        {
          Number*=pow(10,++NB);
        }
        else if(str[i]=='-')
        {
            Number=0-(str[strlen(str)-1]-48);
        }
        else if(i==(strlen(str)-1))
        {
            if(str[0]!='-')
            {
                Number+=str[strlen(str)-1]-48;
            }
            else{
                Number-=str[strlen(str)-1]-48;
            }
        }
    }
    return Number;
}
int main() {
    
    char str[3000]={0};
    gets(str);
    char*p=str;
    int count = 0;
    int arr[1024]={0};
    char TT[30]={0};
    int flag=0;
    do
    {
        while(*p>='0'&&*p<='9'||*p=='-')
        {
        TT[count++]=*p;
        p++;
        }
        count =0;
        arr[flag++]=StoT(TT);
        p++;
        memset(TT,0,sizeof(TT));
    }while(*(p-1));
    swap(arr,flag-1);
   printf("%d",arr[flag/2]);
     return 0;
}

发表于 2023-03-06 23:06:48 回复(0)