NC541 换座位

题目描述：

给你一个环状数组，数组的元素是1,2,3。

要想把它换成所有1相邻，所有2相邻，所有3相邻，至少需要多少人换座？

1. 解法一

要想换成123相邻，需要枚举123的六种排***定先后关系，然后取每种换法的最小值。

首先计算每个数字出现了多少次，用map维护；

接下来计算每种排列需要交换几个数，思路如下：

• 首先不考虑环，计算目标数组三个数最后一位所在下标，记为x,y,z
• 不考虑环计算需要几个数字交换，也就是与预期位置不符的个数；
• 让环转起来，若当前x,y,z分别指向的数就是预定结果，说明上一“格子”错开了，“上一格”不用换，这次要换了，故多换一次，如果等于预定结果的下一位，说明上一“格子”恰好转到对应数字了，少换一次。
• 取每一次“旋转”的最小值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Position int整型vector 
     * @return int整型
     */
    vector<tuple<int, int, int>> vp;
    map<int, int> m;
    
    // 获取把array数组变成排列p所需最小操作次数
    int getCount(vector<int> &array, tuple<int, int, int> p) {
        int k = 0, min_count = INT_MAX, cnt = 0;
        
        int p0 = get<0>(p), p1 = get<1>(p), p2 = get<2>(p);

        // 计算每个数字的最后一位
        int x = m[p0]-1, y = x+m[p1], z = y+m[p2];
        
        // 计算需要换几个数
        for (int j = 0; j < m[p0]; j++) {
            if (array[k] != p0) cnt++;
            k++;
        }
        for (int j = 0; j < m[p1]; j++) {
            if (array[k] != p1) cnt++;
            k++;
        }
        for (int j = 0; j < m[p2]; j++) {
            if (array[k] != p2) cnt++;
            k++;
        }        
        
        min_count = cnt;
        
        // 让环形转起来！
        while (x) {
            // 如果临界点的数恰好和原来相等，说明上一格没换，转过来预期变了，+1
            // 如果和原来预期的下一位相等，说明上一格换了，转过来恰好不需要换了，-1

            if (array[x] == p0) cnt++;
            else if(array[x] == p1) cnt--;
            
            if (array[y] == p1) cnt++;
            else if (array[y] == p2) cnt--;
            
            if (array[z] == p2) cnt++;
            else if (array[z] == p0) cnt--;
            
            min_count = min(cnt, min_count);
            x--,y--,z--;
        }
        
        cout << min_count << endl;
        return min_count;        
    }
    int ChangePosition(vector<int>& Position) {
        // write code here
        vp.push_back({1,2,3});
        vp.push_back({1,3,2});
        vp.push_back({2,1,3});
        vp.push_back({2,3,1});
        vp.push_back({3,1,2});
        vp.push_back({3,2,1});
        
        for (auto a : Position) m[a]++;
        
        int res = INT_MAX;
        for (auto p : vp) {
            int changeCount = getCount(Position, p);
            res = min(res, changeCount);
        }
        
        return res;
    }
};

• 时间复杂度：$O\left(n\right)O(n)$O(n), 遍历了一次数组。
• 空间复杂度：$O\left(1\right)O(1)$O(1), 只有常数个空间

解法二：利用环形的性质

其实利用环形的性质，我们发现一共就两种情况，$1,2,3\{1,2,3\}$1,2,3和$1,3,2\{1,3,2\}$1,3,2, 所以只考虑这两种情况即可。

之前是转$xx$x格，现在x<0可以转到$n-1n-1$n−1号位置，每种情况都转$n-1n-1$n−1格，也是可以的。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Position int整型vector 
     * @return int整型
     */
    vector<tuple<int, int, int>> vp;
    map<int, int> m;
    
    // 获取把array数组变成排列p所需最小操作次数
    int getCount(vector<int> &array, tuple<int, int, int> p) {
        int k = 0, min_count = INT_MAX, cnt = 0;
        int n = array.size();
        int p0 = get<0>(p), p1 = get<1>(p), p2 = get<2>(p);

        int x = m[p0]-1, y = x+m[p1], z = y+m[p2];
        
        for (int j = 0; j < m[p0]; j++) {
            if (array[k] != p0) cnt++;
            k++;
        }
        for (int j = 0; j < m[p1]; j++) {
            if (array[k] != p1) cnt++;
            k++;
        }
        for (int j = 0; j < m[p2]; j++) {
            if (array[k] != p2) cnt++;
            k++;
        }        
        
        min_count = cnt;
        
      	// 从n-1号转到0号
        int m = n - 1;
        
        while (m--) {
            if (array[x] == p0) cnt++;
            else if(array[x] == p1) cnt--;
            
            if (array[y] == p1) cnt++;
            else if (array[y] == p2) cnt--;
            
            if (array[z] == p2) cnt++;
            else if (array[z] == p0) cnt--;
            
            min_count = min(cnt, min_count);
            x = (x-1+n)%n;// 每次转到0号，从数组末尾继续开始转
            y = (y-1+n)%n;
            z = (z-1+n)%n;
        }
        
        return min_count;        
    }
    int ChangePosition(vector<int>& Position) {
        // write code here
        vp.push_back({1,2,3}); // 只要2种情况
        vp.push_back({1,3,2});
        for (auto a : Position) m[a]++;
        
        int res = INT_MAX;
        for (auto p : vp) {
            int changeCount = getCount(Position, p);
            res = min(res, changeCount);
        }
        
        return res;
    }
};

• 时间复杂度：$O\left(n\right)O(n)$O(n), 遍历了一次数组，map里面只有三种key，是$O\left(1\right)O(1)$O(1)的规模，所以用map还是unordered_map没多大区别。
• 空间复杂度：$O\left(1\right)O(1)$O(1), 只有常数个空间