首页 > 试题广场 >

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

[编程题]n个数里出现次数大于等于n/2的数
  • 热度指数:21972 时间限制: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只需要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)

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

#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)
//做的时候没想到中间值的方法,使用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)
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)
既然超过了一半,那么排序之后中间值就肯定是它
import sys

for line in sys.stdin:
    data = sorted([int(i) for i in line.strip('\n').split(' ')])
    print(data[len(data)//2 - 1])
发表于 2017-11-19 17:04:16 回复(3)
#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)
//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)

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)
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)
推荐 看《编程之美》
两种解法
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)

方法一 :枚举法,时间复杂度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)
#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)
/*涉及到奇偶问题以及两个数各占一半的问题*/
#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)
/*看了几页发现竟然没有人用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)
#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)
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)