题解 | #换座位#
换座位
http://www.nowcoder.com/practice/2fd53187e5c94d4f9fa4102c39b194bb
算法思想一：哈希表
解题思路：
根据题意可知，三个人的位置为123，则排列方式有6中：123，132，213，231，312，321，因此只需要检查这六种预定结果需要变换多少次，取其最小值即可，使用到了哈希表记录每个数字出现的次数
检查每个预定结果需要多少次交换的时候，需要调用getmin函数，利用贪心思想，
1、首先看原数组与预定结果之间有多少位的差别
2、然后比较从每个预定结果的末尾位开始比较，若是相同则因为交换的时候跳过了，则交换次数加1，若是刚好等于预定结果的后一个数字，则交换次数减1，因为它的位置是正确的
3、最后更新最小的交换次数
图解：
代码展示：
JAVA版本
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param Position int整型一维数组
* @return int整型
*/
public int ChangePosition (int[] Position) {
// write code here
// 哈希表统计每个数字出现的次数
Map<Integer, Integer> map = new HashMap<>();
map.put(1, 0);
map.put(2, 0);
map.put(3, 0);
for (int i : Position) {
map.put(i, map.get(i) + 1);
}
int[][] Lists = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};
int min = Integer.MAX_VALUE;
for (int[] ints : Lists) {
// 遍历每一种情况。找到最小值
int s = getmin(Position, map, ints);
min = Math.min(min, s);
}
return min;
}
private int getmin(int[] Position, Map<Integer, Integer> map, int[] L) {
int k = 0, cnt = 0, Min = 0;
for(int i = 0; i < 3; i++){
for(int j = 0; j < map.get(L[i]); j++){
// 预定的位置不符合的数量
if(Position[k] != L[i])
cnt++;
k++;
}
}
Min = cnt;
// 每个数字预定模板中的结束下标
int x = map.get(L[0]) - 1, y = x + map.get(L[1]), z = y + map.get(L[2]);
for( ; x > 0; x--, y--, z--){
// 每一位比较
if(Position[x] == L[0])
cnt++;
else if(Position[x] == L[1])
cnt--;
if(Position[y] == L[1])
cnt++;
else if(Position[y] == L[2])
cnt--;
if(Position[z] == L[2])
cnt++;
else if(Position[z] == L[0])
cnt--;
Min = Math.min(Min, cnt);
}
return Min;
}
} 复杂度分析
时间复杂度)
：
为数组长度，因为都是一次遍历
空间复杂度)
：虽然借助哈希表和辅助数组，但是辅助数组Lists只有18个变量，哈希表只使用了3个空间
算法思想二：优化
解题思路：
因为题目说的这是一个循环，因此123和132两个预定结果就可以代替所有六种：
123 = 312 = 231
132 = 321 = 213
因此可以对方法一优化成只有两种情况，再类似比较两种情况的较小值。因为要用循环来比较，因此比较的时候下标需要取模运算。
123 = 312 = 231
132 = 321 = 213
因此可以对方法一优化成只有两种情况，再类似比较两种情况的较小值。因为要用循环来比较，因此比较的时候下标需要取模
代码展示：
Python版本
class Solution: def ChangePosition(self , Position ): # write code here n = len(Position) # 统计每个数字出现的次数 count_1 = 0 count_2 = 0 count_3 = 0 for p in Position: if p == 1: count_1+=1 elif p == 2: count_2+=1 else: count_3+=1 window_123 = 0 window_132 = 0 for i, p in enumerate(Position): # 统计与两个预定结果不同位置数 if i < count_1: if not p == 1: window_123+=1 window_132+=1 else: if count_1 <= i < count_1+count_2: if not p == 2: window_123+=1 else: if not p == 3: window_123+=1 if count_1 <= i < count_1+count_3: if not p == 3: window_132+=1 else: if not p == 2: window_132+=1 result = min(window_123,window_132) # 遍历和方法一样。开始一一调换 for i in range(1,n): if Position[(i-1)%n] == 1: window_123+=1 window_132+=1 if Position[(count_1-1+i)%n] == 1: window_123-=1 window_132-=1 if Position[(count_1-1+i)%n] == 2: window_123+=1 if Position[(count_1+count_2-1+i)%n] == 2: window_123-=1 if Position[(count_1-1+i)%n] == 3: window_132+=1 if Position[(count_1+count_3-1+i)%n] == 3: window_132-=1 if Position[(count_1+count_2-1+i)%n] == 3: window_123+=1 if Position[(count_1+count_2+count_3-1+i)%n] == 3: window_123-=1 if Position[(count_1+count_3-1+i)%n] == 2: window_132+=1 if Position[(count_1+count_2+count_3-1+i)%n] == 2: window_132-=1 result = min(result, window_132, window_123) return result
复杂度分析
时间复杂度：为数组长度，三次单层遍历
空间复杂度：仅使用常数级空间
西门子公司氛围 36人发布