騰訊//求衆數

給定一個大小為 n 的數組，找到其中的衆數。衆數是指在數組中出現次數大于 

⌊ n/2 ⌋

 的元素。

你可以假設數組是非空的，并且給定的數組總是存在衆數。

示例 1:

輸入: [3,2,3]
輸出: 3      

示例 2:

輸入: [2,2,1,1,1,2,2]
輸出: 2      

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if(nums.size()==1)
            return nums[0];
        map<int,int> tables;
        for(int i = 0; i < nums.size(); i++){
            if(tables.count(nums[i])){
                tables[nums[i]]++;
                if(tables[nums[i]]>nums.size()/2)
                          return nums[i];
            }else{
                tables[nums[i]] = 1;
            }
        }
    }
};           

class Solution {
    // 衆數求解算法
    public int majorityElement(int[] nums) {
        // 黑闆(用于記錄資料用)
        LinkedHashMap<Integer, Integer> blackboard = new LinkedHashMap<>();
        // 左邊記錄到的位置
        int leftPs = 0;
        // 右邊記錄到的位置
        int rightPs = nums.length - 1;
        // 衆數
        Integer mode = null;

        tag: while (leftPs <= rightPs) {
            for (int i = leftPs; i <= rightPs; i++) {
                if (blackboard.get(nums[i]) == null) {
                    blackboard.put(nums[i], 1);
                    leftPs = i + 1;
                    if (leftPs > rightPs) {
                        mode = nums[i];
                    }
                    break;
                } else {
                    int count = blackboard.get(nums[i]);
                    count++;
                    if (count>nums.length/2) {
                        mode = nums[i];
                        break tag;
                    }
                    blackboard.put(nums[i], count);
                }
            }
            for (int i = rightPs; i >= leftPs; i--) {
                if (blackboard.get(nums[i]) == null) {
                    blackboard.put(nums[i], 1);
                    rightPs = i - 1;
                    if (rightPs < leftPs) {
                        mode = nums[i];
                    }
                    break;
                } else {
                    int count = blackboard.get(nums[i]);
                    count++;
                    if (count>nums.length/2) {
                        mode = nums[i];
                        break tag;
                    }
                    blackboard.put(nums[i], count);
                }
            }
        }
        return mode;
    }
}