首页 > 试题广场 > 查找数组众数
[编程题]查找数组众数

给定一个数组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 回复(0)
√头像
 
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)
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)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
 
    public static void main(String[] args) {
        Main test3=new Main();
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            String input=sc.next();
            String str=input.substring(1,input.length()-1);
            String[] strArr=str.split(",");
            int[] arr=test3.processLine(strArr);
            System.out.println(test3.MajorElement(arr));
             
             
        }
 
    }
     
    public int MajorElement(int[] arr){
        Arrays.sort(arr);
        return arr[arr.length/2];
         
    }
     
    //将string类型数组,转换为int类型数组
    private int[] processLine(String[] strings) {
        int[] intArray=new int[strings.length];
        int i=0;
        for(String str:strings) {
            intArray[i]=Integer.parseInt(str);
            i++;
        }
        return intArray;
    }
 
}

发表于 2019-09-30 14:49:30 回复(0)
"""
思路:排序后,中间的数一定是众数
"""
inp=list(map(int,input().replace('[','').replace(']','').split(',')))
inp=sorted(inp)
index=len(inp)//2
print(inp[index])    #排序后,中间的数一定是众数


发表于 2019-09-13 01:30:28 回复(0)
from collections import Counter

nums = list(map(int, input()[1:-1].split(",")))
cnt = Counter(nums)
for k, v in cnt.items():
    if v > len(nums) / 2:
        print(k)
        break

发表于 2019-09-03 10:36:21 回复(0)
arr = input() if ',' not in arr:
    arr = arr[1:-1] print(arr) else:
    numbers = list(map(str, arr.split(',')))
    numbers[0] = numbers[0][1:]
    numbers[-1] = numbers[-1][:-1]
    numbers = list(map(int, numbers))
    numbers = sorted(numbers)
    n = len(numbers) print(numbers[int(n//2)])
发表于 2019-09-02 16:34:14 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main() {
	string str;
	cin >> str;
	int len = str.length();
	str = str.substr(1, len - 2);
	vector<string> arr;

	while(-1 != (int)str.find(",")){
		arr.push_back(str.substr(0, str.find(",")));
		str = str.substr(str.find(",") + 1);
	}
	arr.push_back(str);
	sort(arr.begin(), arr.end());
	cout << arr[arr.size() / 2];
	return 0;
}

发表于 2019-08-30 15:32:41 回复(0)
#### 方法1
# 由于要超过n/2次才是众数,因此排序后,中间位置上的一定是众数
a = input()[1:-1]
a = list(map(int,a.split(',')))
a = sorted(a)
print(a[len(a) // 2])

#### 方法2
# eval() 函数用来执行一个字符串表达式,并返回表达式的值。
s = eval(input())
for i in s:
    # count()函数用于统计字符串里某个字符出现的次数
    # 语法 str.count(sub, start= 0,end=len(string))
    if s.count(i) > int(len(s)/2):
        print(i)
        break

发表于 2019-08-19 16:23:03 回复(0)
num = eval(input())
num.sort()
l = len(num)//2
print(num[l])

发表于 2019-07-29 10:45:36 回复(0)
# include <iostream>
# include <map>
# include <algorithm>
using namespace std;
int main()
{
    char c;
    while(cin >> c)
    {
        int t,x,l=0;
        char d;
        map<int, int> m;
        while(cin >> x >> d )
        {
            l++;
            m[x]++;
            if(d==']')
                break;
        }
        map<int, int>::iterator iter = m.begin();
        for (; iter != m.end(); iter++)
        {
             if(iter->second > l/2)
                 cout << iter->first << endl;
        }
    }
    return 0;
}

发表于 2019-07-17 15:09:09 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
          String str1=str.substring(1,str.length()-1);
 
            String ss[]=str1.split(",");
        
        int ss1[] = new int[ss.length];
    for(int i = 0; i < ss.length; i++){
        ss1[i] = Integer.valueOf(ss[i]);
    }
        System.out.println(getZhong(ss1));
 }
    private static int getZhong(int[] ss1){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < ss1.length; i++){
            if(map.containsKey(ss1[i])){
                map.put(ss1[i], map.get(ss1[i]) + 1);
            }else{
                map.put(ss1[i], 1);
            }
        }
        int max = 0;
        int max1 = 0;
        int tmp = 0;
        for(Integer num : map.keySet()){
            tmp = map.get(num);
            if(tmp > max){
                max = tmp;
                max1 = num;
 
            }
        }
        return max1;
    }
     
}

发表于 2019-07-11 02:05:17 回复(0)
arrs = list(map(int, input()[1:-1].split(',')))
temp,num = arrs[0],1
for i in range(1,len(arrs)):
    if num==0:
        temp = arrs[i]
        num=1
    elif arrs[i]!=temp:
        num-=1
    else:
        num+=1
print(temp)

发表于 2019-07-10 10:17:36 回复(0)