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 + "]";
    }
}