题解 | #换座位#

思路：

题目的主要信息：

• 一个循环的圈，即数组首尾相接，数组中只有1 2 3三种元素
• 要使这三种元素相同的元素都排在一起，即类似111122222333或者112222233311
• 123的顺序不限

方法一：哈希表+贪心
具体做法：
因为123的顺序不限，因此我们的结果有6中排列组合方式，分别是：
123
132
213
231
312
321
因为我们只需要检查这六种预定结果需要变换多少次，取其最小值即可，其中我们使用到了哈希表记录每个数字出现的次数。
检查每个预定结果需要多少次交换的时候，我们调用findMin函数，利用贪心思想，首先我们看原数组与预定结果之间有多少位的差别，然后比较从每个预定结果的末尾位开始比较，若是相同则因为交换的时候跳过了，结果要加一，若是刚好等于预定结果的后一个数字，则结果减一，因为它的位置是正确的，我们算的交换次数。
findMin函数如下图所示：

class Solution {
public:
    int findMin(vector<int>& Position, map<int, int>& m, int *a){
        int k = 0, cnt = 0, res = 0;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < m[a[i]]; j++){
                if(Position[k] != a[i])  //预定的位置不符合的数量
                    cnt++;
                k++;
            }
        }
        res = cnt;
        int x = m[a[0]] - 1, y = x + m[a[1]], z = y + m[a[2]];  //每个数字预定模板中的结束下标
        for(; x > 0; x--, y--, z--){ //每一位比较
            if(Position[x] == a[0])
                cnt++;
            else if(Position[x] == a[1])
                cnt--;
            if(Position[y] == a[1])
                cnt++;
            else if(Position[y] == a[2])
                cnt--;
            if(Position[z] == a[2])
                cnt++;
            else if(Position[z] == a[0])
                cnt--;
            res = min(res, cnt);
        }
        return res;
    }
    int ChangePosition(vector<int>& Position) {
        map<int, int> mp;  //哈希表统计每个数字出现的次数
        int n = Position.size();
        for(int i = 0; i < n; i++)
            mp[Position[i]]++;
        int res = INT_MAX;
        int L[6][3] = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}; //6种次序
        for(int i = 0; i < 6; i++){ //遍历每一种次序，找到最小值
            int s = findMin(Position, mp, L[i]);
            res = min(res, s);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，为数组长度，因为都是一次遍历
• 空间复杂度：，虽然借助哈希表和辅助数组，但是辅助数组L只有18个变量，哈希表只使用了3个空间

方法二：优化方法一
具体做法：
因为题目说的这是一个循环，因此123和132两个预定结果就可以代替所有六种：
123 = 312 = 231
132 = 321 = 213
因此我们可以对方法一优化成只有两种情况，再类似比较两种情况的较小值。因为要用循环来比较，因此我们比较的时候下标需要取模运算。

class Solution {
public:
    int ChangePosition(vector<int>& Position) {
        int n = Position.size();
        int count1 = 0, count2 = 0, count3 = 0; //统计每个数字出现的次数
        for (int i = 0; i < n; i++) {
            if (Position[i] == 1)
                count1++;
            else if (Position[i] == 2)
                count2++;
            else
                count3++;
        }
        int win123 = 0, win132 = 0;
        for (int i = 0; i < n; i++){  //统计与两个预定结果不同位置数
            if (i < count1) {
                if (Position[i] != 1) {
                    win123++;
                    win132++;
                }
            }
            else {
                if (i < count1 + count2){
                    if (Position[i] != 2)
                        win123++;
                }
                else{
                    if (Position[i] != 3)
                        win123++;
                }
                if (i < count1 + count3){
                    if (Position[i] != 3)
                        win132++;
                }
                else{
                    if (Position[i] != 2)
                        win132++;
                }
            }
        }
        int res = min(win123, win132);
        for(int i = 1; i < n; i++){ //遍历类似方法一开始调换
            if(Position[(i - 1) % n] == 1){
                win123++;
                win132++;
            }
            if(Position[(count1 - 1 + i) % n] == 1){
                win123--;
                win132--;
            }
            if(Position[(count1 - 1 + i) % n] == 2)
                win123++;
            if(Position[(count1 + count2 - 1 + i) % n] == 2)
                win123--;
            if(Position[(count1 - 1 + i) % n] == 3)
                win132++;
            if(Position[(count1 + count3 - 1 + i) % n] == 3)
                win132--;
            if(Position[(count1 + count2 - 1 + i) % n] == 3)
                win123++;
            if(Position[(count1 + count2 + count3 - 1 + i) % n] == 3)
                win123--;
            if(Position[(count1 + count3 - 1 + i) % n] == 2)
                win132++;
            if(Position[(count1 + count2 + count3 - 1 + i) % n] == 2)
                win132--;
            res = min(res, win123); //维护最小值
            res = min(res, win132);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，三次单层遍历
• 空间复杂度：，常数空间