首页 > 试题广场 >

n个数里出现次数大于等于n2的数

[编程题]n个数里出现次数大于等于n/2的数
  • 热度指数：22132 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
输入n个整数，输出出现次数大于等于数组长度一半的数。

输入描述:
每个测试输入包含 n个空格分割的n个整数，n不超过100，其中有一个整数出现次数大于等于n/2。


输出描述:
输出出现次数大于等于n/2的数。
示例1

输入

3 9 3 2 5 6 7 3 2 3 3 3

输出

3
算法知识视频讲解
添加回答
Python
华科平凡头像 华科平凡

Python只需要3行就能通过：
利用collections的Counter模块，跟切菜一样简单：

from collections import Counter
c = Counter(list(map(int, input().split())))
print(c.most_common(1)[0][0])
发表于 2017-09-07 13:55:10 回复(3)
C/C++
卷积神经网络哦头像 卷积神经网络哦

这种题目数字大一点必须用哈希 数字小的***搞都可以

#include <iostream>
using namespace std;
int ha[105], a[105];
int main(){
    int n = 0;
    while(scanf("%d", &a[n]) == 1) {
        ha[a[n]]++; n++;
    }
    for(int i = 0; i < n; i++)
        if(ha[a[i]] >= n/2) {printf("%d\n", a[i]); break;}
    return 0;
}
发表于 2018-09-18 12:09:06 回复(0)
Java
中南的小菜鸡头像 中南的小菜鸡 
//做的时候没想到中间值的方法，使用map的方法如下
import java.util.Scanner;
import java.util.Map;
import java.util.TreeMap;
import java.util.Map.Entry;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            Map<Integer,Integer> map = new TreeMap<>();
            String[] strs = sc.nextLine().split(" ");
            for(int i=0;i<strs.length;i++){
                int s = Integer.valueOf(strs[i]);
                if(map.containsKey(s)){
                    map.put(s,map.get(s)+1);
                }else{
                    map.put(s,1);
                }
            }
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
                if(entry.getValue() >= strs.length/2){
                    System.out.println(entry.getKey());
                }
            }
        }
    }
}

发表于 2018-10-29 19:02:06 回复(0)
dragonhaw头像 dragonhaw 
import java.util.*;
/**
 * 剑指offer原题
 * 
 * @author 何嘉龙
 *
 */
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			String str = in.nextLine();
			String[] strs = str.split(" ");
			int[] arr = new int[strs.length];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = Integer.valueOf(strs[i]);
			}
			int num = arr[0];
			int count = 0;
			for (int j = 1; j < arr.length; j++) {
				if (arr[j] == num) {
					count++;
				} else if (count > 0) {
					count--;
				} else {
					num = arr[j];
				}
			}
			System.out.println(num);
		}
	}
}

编辑于 2017-08-16 14:29:11 回复(9)
假面英雄暗律头像 假面英雄暗律
#include<stdio.h>
int main(){
    int tem,flag,cou=0;
    char ch;
    while(~scanf("%d%c",&tem,&ch)){
            if(cou==0)flag=tem;
            if(flag==tem)cou++;
            else cou--;
        if(ch=='\n'){
            printf("%d\n",flag);
            cou=0;
        }
    }
}
发表于 2018-03-20 14:54:13 回复(0)
向宇左桌头像 向宇左桌 
O(n)~
#include<stdio.h>
#include<stdlib.h>

int main()
{
	int a[105];
    int i = 0;
    while(~scanf("%d",&a[i])){
        i++;
    }
    int num = a[0];
    int cnt = 0;
    for(int j = 1 ; j < i ; ++j){
        if(a[j] == num){
            cnt++;
        }else if(cnt>0){
            cnt--;
        }else{
            num = a[j];
        }
    }
    printf("%d\n", num);
    return 0;
}

发表于 2017-08-08 23:45:16 回复(5)
C/C++
神山极客头像 神山极客 
//O(n)思想：因为要找过半的数，用一个变量count记录读取每个变量变化的次数，
//一个变量temp记录可能过半的数，先让count=1，然后让temp=vec[0]，
//然后往后遍历一遍，碰到和temp相同的数就给count++，否则就count--
//如果，count变成0，就让temp=vec[i](vec数组遍历过程当前值),并让count=1
//如此遍历一遍，因为有一个数过半，所以temp最后肯定存储的是过半的数
#include <bits/stdc++.h> 
using namespace std;
int main(){
    int n;
    vector <int> vec;
    while(cin >> n) vec.push_back(n);
    int count = 1;
    int temp = vec[0];
    for(int i = 1; i < vec.size(); ++i){
        if(vec[i] == temp) count++;
        else count--;
        if(count == 0) temp = vec[i], count++;//(逗号表达式，懒得写大括号)
    }
    cout << temp << endl;
    return 0;
}

编辑于 2017-09-06 02:22:11 回复(8)
Java
亘头像 亘

import java.util.Scanner;
//输入n个整数，输出出现次数大于等于数组长度一半的数。
//输入描述:
//
//每个测试输入包含 n个空格分割的n个整数，n不超过100，其中有一个整数出现次数大于等于n/2。
//
//输出描述:
//
//输出出现次数大于等于n/2的数。
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        String[] strings = string.split(" ");
        for (int i = 0; i < strings.length; i++) {
            int sum = 0;
            for (int j = 0; j < strings.length; j++) {

                if (strings[i].equals(strings[j])) {
                    sum++;
                }
                }
              int s=strings.length/2;
                if (sum >= s) {
                    System.out.println(strings[i]);
                    break;
                }
            

        }
    }

}

发表于 2017-11-07 11:39:26 回复(0)
qianhuan头像 qianhuan 
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    //如果这个数出现的次数超过一半 排序后数组中间的数必定是它
//    public static int getCountHalfLen(int[] arr){
//        Arrays.sort(arr);
//        return arr[arr.length/2];
//    }
    
    public static int getCountHalfLen(int[] arr){
        int[] count = new int[arr.length]; //count[i]表示索引为i出现的次数,统计每个数出现的次数
        for (int i = 0; i < count.length; i++) {
            for (int j = 0; j < count.length; j++) {
                if(arr[i] == arr[j]) count[i]++;
            }
        }

        for (int i = 0; i < count.length; i++) {
            if(count[i] >= (arr.length + 1)/2) return arr[i];
        }
        return 0;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String dataStr = sc.nextLine();
        String[] split = dataStr.split(" ");
        int[] arr = new int[split.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }
        System.out.println(getCountHalfLen(arr));
    }
}

编辑于 2018-02-23 16:26:47 回复(12)
顾钧菲头像 顾钧菲 
"""
Python 2 分钟搞定
"""
import re
output=""
input_val = re.split(" ",raw_input())
set_val = set(input_val)

for num in set_val:
    count_num = input_val.count(num)
    if count_num >= len(input_val)/2:
        output = output + num + " "
print (output[:-1])

发表于 2017-04-01 09:17:44 回复(1)
牛客671653号头像 牛客671653号
推荐 看《编程之美》
两种解法
1. 给定得数组排序， 第 N/2 个 肯定是要求得

2.逐个计数法 o(N) 

	publicstaticvoidmain(String[] args) {





	        Scanner sc = newScanner(System.in);





	        String str = sc.nextLine();





	        String [] arrays = str.split(" ");





	         





	         





	        intnTime,id = Integer.MIN_VALUE;





	        for(inti= nTime = 0;i<arrays.length;i++){





	            if(nTime == 0){





	                id = Integer.valueOf(arrays[i]);





	                nTime = 1;





	            }else{





	                if(id == Integer.valueOf(arrays[i]) ){





	                    ++ nTime;





	                }else{





	                    -- nTime;





	                }





	            }





	        }





	        System.out.println(id);





	         





	        sc.close();





	    }

发表于 2017-02-15 11:31:51 回复(0)
C/C++
51Hz头像 51Hz

方法一 ：枚举法，时间复杂度O（n2）

依次比较每个数出现的次数，记下出现次数最多的值，如果出现次数大于个数的一半，返回它。
  1. int  majorityNumber(vector< int > nums) {  
  2.         // write your code here   
  3.         int  n = nums.size();  
  4.         int  times1 = 0;  
  5.         int  times2 = 0;  
  6.         int  index =0;  
  7.         for ( int  i=0; i<n; i++)  
  8.         {  
  9.             for ( int  j=0; j<n; j++)  
  10.             {  
  11.                 if (nums[i] == nums[j])  
  12.                     times1++;  
  13.             }  
  14.             if (times1 > times2)  
  15.             {  
  16.                 times2 = times1;  
  17.                 index = i;  
  18.             }  
  19.             times1 = 0;  
  20.         }  
  21.         if (times2 > n/2)  
  22.         {  
  23.             return  nums[index];  
  24.         }  
  25.     }  
方法二 ：将数组进行排序，转化为有序序列，如果存在主元素，则一定是序列的中位数。

这样时间复杂度取决于排列方法 + 遍历判断次数是否大于一半。

时间复杂度：排列O（nlogn）+遍历O（n） = O（n）

代码略…

发表于 2017-02-15 17:41:58 回复(4)
C/C++
WZ_Dale头像 WZ_Dale 
#include <iostream>

using namespace std;

int main(){
    int cur, save;
    cin >> save;
    int count = 1;
    while(cin >> cur){
        cur == save ? ++count : --count;
        if(count == 0){
            save = cur;
            count = 1;
        }
    }
    cout << save;
    return 0;
}

编辑于 2020-05-29 11:22:33 回复(0)
金金金m头像 金金金m 
/*涉及到奇偶问题以及两个数各占一半的问题*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[100] = { 0 }, b[100] = { 0 };
    int n, i = 0, j, num = 0, temp;
    while (cin >> n)
    {
        b[i++] = n;
        a[n]++;
    }
    int f=i;
    for (j = 0; j < i; j++)
    {
        if(i%2==1) //总数为奇数的情况，不存在两个数各占一半的状况
        {
             if (a[b[j]] > i / 2)//重复次数大于长度一半
            {
                cout << b[j] << endl;
                break;//如果重复次数大于长度一半，那么只能有一个数满足，所以直接跳出。
            }
        }
        else//总数为偶数的情况，存在各占一半的情况
        {
            bool flag = true;
            if (a[b[j]] > i / 2)//重复次数大于长度一半
            {
                cout << b[j] << endl;
                break;//如果重复次数大于长度一半，那么只能有一个数满足，所以直接跳出。
            }
            else if (a[b[j]] == i / 2 )//重复次数等于长度一半
            {
                cout << b[j] << endl;
                for(int k=0;k<f;k++)
                {
                    if(b[k] != b[j])
                    {
                        if(a[b[k]] == i / 2)
                        {
                            cout<<b[k] << endl;
                            flag=false;
                            break;
                        }
                        else
                        {
                            flag=false;
                            break;
                        }
                    }
                }
                if(flag == false)
                {
                    break;
                }
            }
        }
    }
}

编辑于 2019-04-22 11:02:12 回复(0)
不强化学习头像 不强化学习 
//输入数组a后对a排序，数组中间的数就是我们要找的
#include<iostream>
#include<algorithm>
using namespace std;
#define MaxSize 101
int main()
{
    int a[MaxSize];
    int j = 0;
    while (cin >> a[j]){
        j++;
    }
    sort(a, a + j);
      int m=j/2-1;
    cout <<a[m]<<endl;
    return 0;
}

编辑于 2019-04-18 22:41:26 回复(0)
晓色竹韵头像 晓色竹韵
#include <iostream>
using namespace std;
int main()
{
int a[100] = { 0 }, b[100] = { 0 };
int n, i = 0, j, num = 0, temp;
while (cin >> n)
{
b[i++] = n;
a[n]++;
}
for (j = 0; j < i; j++)
{
if (a[b[j]] > i / 2)//重复次数大于长度一半
{
cout << b[j] << endl;
break;//如果重复次数大于长度一半，那么只能有一个数满足，所以直接跳出。
}
else if (a[b[j]] == i / 2 )//重复次数等于长度一半
{
cout << b[j] << endl;
temp = b[j];//如果重复次数等于长度一半，那么还要考虑另外一半是不是也是一个数。比如输入6、8，那么要输出6、8两个数。
while (b[++j] == temp);
if(a[b[j]] == i / 2)
cout << b[j] << endl;
break;
}
}
return 0;
}
编辑于 2018-07-24 11:21:38 回复(0)
Vincent_Su头像 Vincent_Su 
/*看了几页发现竟然没有人用STL的set或者map去做这道题目，开数组去做这道题目大概率不好，
一旦输入数字较大那扫描的时候就比较耗时；而且看了好几个人的实现，利用cnt和temp去
统计的方法在面对一些零散的排列的时候都有可能出现问题，例如这些解法评论里的
2 3 4 3 5这种排列往往得到的就是最后一个数5而不是3.当然排序的方法很粗暴，个人很喜欢hhhhh，
但是还是想写一个更简单的，这道题用map去实现，利用键值对的方法比较清晰，而且不需要开很大
的数组，左值存储数字，右值存储该数字的出现次数，最后用一个迭代器判断右值就OK了呀*/


	#include <bits/stdc++.h>
using namespace std;





	int main()
{
 int n,cnt=0;
 map <int,int> num;
 while(cin >> n)
 {
  num[n]++;
  cnt++;
 }
 
 for(map<int,int>::iterator it=num.begin();it!=num.end();it++)
 {
  if((it->second)>=(cnt/2))
   cout << it->first;
 }
 return 0;
}

编辑于 2018-07-20 13:23:17 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>

using namespace std;

int main()
{     int n, count=0, a[1010] = {0};     while(cin>>n)     {         a[n]++;         count++;     }     for(int i=0;i<count;i++)     {         if(a[i]>=count/2)             cout<<i<<endl;     }     return 0;
}

发表于 2018-01-03 02:01:18 回复(0)
Java
牛顿的苹果头像 牛顿的苹果
import java.util.*;
public class Main{
public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String str=scan.nextLine();
            String[]sc=str.split(" ");
            int[]arr=new int[sc.length];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = Integer.valueOf(sc[i]);
            }
            Arrays.sort(arr);
            System.out.println(arr[arr.length/2-1]);
        }
        
    }
}
算法不太难，也是想了很久啊
发表于 2018-01-01 14:23:37 回复(1)
Java
老味道头像 老味道
这个题目和我之前在编程之美上看见的id问题差不多。思路：首先将输入的数据分割得到String数组，在这个数组里面至多有一个数字出现的次数大于数组长度的一半，假设存在一个这样的数flag，并在这些数组里面每次选择两个不同的数丢弃，剩下的数中那个flag出现的次数一定还占数组长度的一半（举例：数组长度10,8出现的次数为6，不管丢弃的数有没有含8这个数，剩下的8个数中，8出现的次数一定大于它的一半）。按照这样的思路一直进行下去直到没有两个不同的数时，那么剩下的数中一定全是flag。（假设长度为100，flag出现的次数为51。最极端的情况下flag被丢弃49，剩下的2个相同，所以一定能的到flag的值）代码的实现就是设置一个flag一直比较下面的数比较，如果相同将temp++，不相同的将temp--，因为flag的出现的次数大于总长度的一半，所以总有一个位置上的flag会被留到最后，因为flag出现的后temp一定是大于1的.在判断后输出就好。 

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String[] input = in.nextLine().split(" ");
        int n = input.length;
        int temp = 0;
        String flag=null;
        for(String s:input){
            if(temp==0){
                flag = s;
                temp=1;
            }else if(flag.equals(s)){
                temp++;
            }else{
                temp--;
            }
        }
        if(temp>1){
            System.out.println(flag);
        }
    }
}

发表于 2017-12-14 20:34:05 回复(0)
提交观点

问题信息

C++工程师 2017 数组 好未来 查找 Java工程师
难度：
205条回答 29513浏览

热门推荐

通过挑战的用户

查看代码

相关试题

n个数里出现次数大于等于n/2的数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号