问题描述: 输入 n 个数, 其中一个数的个数大于等于 n/2, 请输出那个数
例如:
输入:
- 18
- 3 3 5 4 3 2 4 2 3 3 4 5 2 13 3 3 3 3
输出: 3
第一种方法: 用 map 集合做, key-value 分别对应数组元素和出现次数, 代码如下:
- /**
- *
- * @param arr 传入数组
- * @param n 数组长度
- */
- public static void code(int[] arr,int n){
- Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
- for(int i = 0;i<n;i++){
- if(!mp.containsKey(arr[i])){
- int count = 0;
- mp.put(arr[i],++count);
- for(int j = i+1;j<n;j++){
- if(arr[j] == arr[i]){
- mp.put(arr[j],++count);
- }
- }
- }
- }
- for(Map.Entry<Integer,Integer> e : mp.entrySet()){
- // 这块 if 判断需要注意的是, 当数组长度为奇数时, 获取的 value 值要大于 n/2. 为偶数大于等于 n/2
- if(e.getValue()>n/2 && n%2 == 1 || e.getValue()>=n/2 && n%2 == 0){
- System.out.println(e.getKey());
- return;
- }
- }
- }
第二种方法:
先看下面几个例子, 蓝色是下标, 先对输入数组排序 (升序)
偶数个元素
0 1 2 3 4 5
1 1 1 2 2 3 这个输出 1
1 2 2 3 3 3 这个输出 3
1 2 2 2 3 3 这个输出 2
奇数个元素
0 1 2 3 4
1 1 1 2 2 这个输出 1
1 2 2 2 3 这个输出 2
从上面的例子可以看出, 当数组长度为奇数时, 直接返回下标为 n/2 的值, 当数组长度为偶数时, 如果第一个元素和 n/2-1 下标对应元素相等就返回第一个元素, 否则返回下标为 n/2 的值, 代码如下:
- public class Main {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- System.out.println("请输入数组大小");
- int n = sc.nextInt();
- int[] arr = new int[n];
- for(int i = 0;i<n;i++){
- arr[i] = sc.nextInt();
- }
- Arrays.sort(arr);
- if(n%2 == 0 &&arr[n/2-1] == arr[0]){
- System.out.println(arr[0]);
- }else{
- System.out.println(arr[n/2]);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3070669.html