描述

牛家村准备开会选举新任村长，村长安排了一个位置表Position（桌子是圆桌！！！所以第一个人和最后一个人是挨着坐的）。村长的候选人牛牛，牛妹，牛大三个。
为了让选举进行的更加顺利，村长想让三位的支持者分别坐在一起。 他想知道最少多少人需要换座位才能使得三类支持者都分别坐在一起。
返回一个整数代表最少多少人需要换座位才能使得三类支持者都分别坐在一起。

示例1

输入： 
[1,2,2,1,3]
复制
返回值： 
2
复制
说明： 
将最后一个人与倒数第二个人的位置互换

备注： 

给定 Table数组 Position_{i}\in {1,2,3}Positioni∈1,2,3 1代表牛牛阵营，2代表牛大阵营，3代表牛妹阵营 1 \leq Position.size \leq 10^{5}1≤Position.size≤105


解题思路：
使用哈希map+贪心算法
1）题目没有固定1，2，3出现的次序，故有6种可能的次序都需要考虑 
list[6][3] = {{1,2,3}, {1,3,2}, {2,3,1}, {2,1,3}, {3,1,2}, {3,2,1}};
我们需要确定的是使用上面6种中的哪种次序换座位次数最少；将上面6种次序分别作为预期次序带入计算；
2）使用map记录1，2，3分别出现的次数；
3）计算不考虑环形座位时需要交换的次数，即使用map记录的结果、带入list预期次序，与实际排列进行对比，不满足预期的即为需要换作为的，统计结果计为res；
4）在3的基础上加上对环形座位的考虑，计算换位结果为cnt；
5）min(res， cnt) 


class Solution {
public:
    int findMin(vector<int>& Position, map<int, int>& smap, int *list) {
        int cnt = 0;
        int res = 0;
        int k = 0;
        // 先统计全部元素不在预期位置的个数，最坏情况为所有不在预期位置的元素都要换位
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < smap[list[i]]; j++) {
                if (Position[k] != list[i]) {
                    cnt++;
                }
                k++;
            }
        }
        res = cnt;
        // 每个元素预期的结束索引
        int x = smap[list[0]] - 1;
        int y = x + smap[list[1]];
        int z = y + smap[list[2]];
        // 下面是考虑首位可相连的情况
        for(;x > 0; x--, y--, z--) {
            if (Position[x] == list[0]) {
                cnt++;
            } else if (Position[x] == list[1]) {
                cnt--;
            }
            if (Position[y] == list[1]) {
                cnt++;
            } else if (Position[y] == list[2]) {
                cnt--;
            }
            if (Position[z] == list[2]) {
                cnt++;
            } else if (Position[z] == list[0]) {
                cnt--;
            }
            res = min(res, cnt);
        }
        return res;
        
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Position int整型vector 
     * @return int整型
     */
    int ChangePosition(vector<int>& Position) {
        // write code here
        map<int, int> smap;
        int n = Position.size();
        for (int i = 0; i < n; i++) {
            (smap[Position[i]])++;
        }
        int res = INT_MAX;
        int list[6][3] = {{1,2,3}, {1,3,2}, {2,3,1}, {2,1,3}, {3,1,2}, {3,2,1}};
        for (int i = 0; i < 6; i++) {
            res = min(res, findMin(Position, smap, list[i]));
        }
        return res;
    }
};