找出一个整数数组中超过数组长度一半的元素(Java)

Question:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字

找出一个整数数组中超过数组长度一半的元素(Java)
package com.study.zhipengs.test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 
 * 例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4,
 * 2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2.
 * 
 * 所有数字的个数均没有超过数组长度的一半,则返回-1
 * 
 * @author zhipegs
 * 
 */
public class Test {
    
    public static void main(String[] args) {
        int[] numbers = { 1, 2, 2, 5, 6, 2, 5, 2, 2};
        System.out.println("number: " + mapSolve(numbers));
        System.out.println("number: " + sortSolve(numbers));
    }

    /**
     * 先排序---排序后统计每个数字出现的次数,出现次数超过数组长度一半的那个一定出现在中间
     * @param numbers
     * @return int
     */
    private static int sortSolve(int[] numbers) {
        Arrays.sort(numbers);
        int count = 0;
        int len = numbers.length;
        int pos = (int) Math.rint((double)len/2.0);
        int midValue = numbers[pos];
        for(int i=0;i<len;i++) {
            if(numbers[i] == midValue) {
                count ++;
                if(count > pos) {
                    return midValue;
                }
            }
        }
        return -1;
    }

    /**
     * 不排序--相同数字存储到Map的key中,个数在value中递增计算
     * @param numbers
     * @return int
     */
    private static int mapSolve(int[] numbers) {
        int len = numbers.length;
        int pos = (int) Math.rint((double)len/2.0);
        Map<String,MyInteger> map = new HashMap<String,MyInteger>();
        MyInteger mi;
        for(int i=0;i<numbers.length;i++) {
            String key = numbers[i]+"";
            mi = map.get(key);
            if(mi != null) {
                int value = mi.get()+1;
                mi.set(value); 
                map.put(key, mi);
                if(value > pos) {
                    return numbers[i];
                }
                continue;
            }
            mi = new MyInteger();
            mi.set(1);
            map.put(key, mi);
        }
        return -1;
    }

}

/**
 * 自定义MyInteger
 */
class MyInteger {
    private int value;

    public void set(int value) {
        this.value = value;
    }

    public int get() {
        return this.value;
    }
    
    @Override
    public String toString() {
        return "MyInteger [value=" + value + "]";
    }
}
找出一个整数数组中超过数组长度一半的元素(Java)

总结:多看书和博客,从别人的代码分享中理解思路,越思越明~~

找出一个整数数组中超过数组长度一半的元素(Java),布布扣,bubuko.com

找出一个整数数组中超过数组长度一半的元素(Java)

上一篇:通过C语言获取MAC地址(转)


下一篇:jQuery同步Ajax带来的UI线程阻塞问题及解决办法