题解 | #微信红包#

import java.util.*;

public class Gift {

    /**
        时间复杂度O(N): 需要遍历数组两次，2N去掉常数项为N。
        空间复杂度O(1): 只需几个常量级的临时变量。
     */
    public int getValue(int[] gifts, int n) {

        // 使用军队比武的思路来实现，这里假设红包金额数一样的属于同一个阵营，从下标0开始遍历数组，
        // 我们约定若遇到相同阵营则战斗力+1，遇到不同阵营则需要与他PK，会造成战斗力-1

        // 变量 winner 来表示当前胜出阵营,
        // 变量 combatValue 表示当前胜出阵营的战斗值

        int winner = 0; 
        int combatValue = 0; 
        
        for(int i = 0; i < n; i++){
            if(combatValue == 0){ // 若当前还没有阵营胜出，则假设gifts[i]先胜出
                winner = gifts[i];
                combatValue++;
                continue;
            }
            if(gifts[i] == winner){ // 是同一个阵营的，则战斗值加1
                combatValue++;
            }else{
                combatValue--; // 不是同一个阵营的，需要进行PK，则战斗值减1
            }
        }

        // 如果确实有某一个红包金额出现的次数超过了总数的一半，则当数组遍历完时，winner就是那个金额
        //（ 因为它干掉了其他所有阵营，他的战力最后还剩1，如用例 [1,1,1,2,2]、[1,1,2,2,1] ）。
        // 注意这里要考虑没有的情况，例如：[1,1,2,2,3]，最后winner是3，但是它并没有超过总数的一半，
        // 所以这里需要统计最后的winner在数组中一共出现的次数是否超过了数组长度的一半。
        int count = 0;
        for(int i = 0; i < n; i++){
            if(gifts[i] == winner){
                count++;
            }
        }
        if(count > (n/2)){
            return winner;
        }else{
            return 0;
        }

        // 这里虽说是军队比武，其实就是人海战术，谁人多谁就赢了，emmmm...
    } 
}