查找数组众数

#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;
}

根据题目中众数的定义，给的数据中一定会出现次数超过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);
    }
}

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))

//排序取中间的那个数
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]);
    	    }
}

# 由题意可判断出最中间的元素一定就是众数了！排序即可
s = map(int,input().strip('[]').split(','))
s = list(s)
s.sort()
print(s[len(s)//2])

#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;
}

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);
        }
    }
}

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);
    }
}

#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;
}

""""
众数(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)

	

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]);
    }
}

#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;
}

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1000
#define MAX_VAL 2000

int main() {
    int arr[MAX_SIZE] = {0};
    int i = 0;
    char input[MAX_SIZE];
    int num;

//录入数组
    fgets(input, sizeof(input), stdin);

    char *ptr = input + 1;

    while (*ptr != ']' && *ptr != '\0') {
        if (isdigit(*ptr) || *ptr == '-' || *ptr == '+') {
            sscanf(ptr, "%d", &num);
            arr[i++] = num;
        }
        while (isdigit(*ptr) || *ptr == '-' || *ptr == '+') ptr++;
        if (*ptr == ',') ptr++;
    }

//寻找出现最多的数(哈希数组思路)
    int count[MAX_VAL] = {0};
    int max_count = 0;

    for (int j = 0; j < i; j++) {
        count[arr[j] + 1000]++;
    }

    for (int m = 0; m < MAX_VAL; m++) {
        if (count[m] > i / 2) printf("%d", m - 1000);
    }

    return 0;
}