题目大意：
距离相等的条形码
在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。
示例 1：
输入：[1,1,1,2,2,2] 输出：[2,1,2,1,2,1]
示例 2：
输入：[1,1,1,1,2,2,3,3] 输出：[1,3,1,3,2,1,2,1]
提示：
1 <= barcodes.length <= 100001 <= barcodes[i] <= 10000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1054
解题思路分析：
题目要求很明确，重新排列数组，使得相邻的两个数字不能相同。我们可以考虑使用分组的方式，将相同的元素分到不同的组中，这样就能够保证每一个组中不存在相同元素，然后再将所有组合并起来即可。
举个例子，比如我们有2个1，3个2，4个3。将数组排序后如下：
[1, 1, 2, 2, 2, 3, 3, 3, 3]
先找出个数最多的元素，以这个最大个数分组。比如上例中3的个数最多，有4个，我们就将所有数字分成4组，先将每一组加入一个数字3。（这样做的理由是，如果我们要保证每种相同数字不相邻，那么要先保证个数最多的元素不能相邻，也就是说他们之间要有其他数字作为间隔。注意：如果其他数字的个数总和小于这个最大个数，比如1个1，100个2的情况，是不存在解的，本题并没有说明这种情况该如何对应，因此不考虑。）
[3] [3] [3] [3] // 剩余[1, 1, 2, 2, 2]
然后再将剩余数字按顺序添加到每个组中。
[3, 1] [3] [3] [3] // 添加一个1，剩余[1, 2, 2, 2] --------------------------------- [3, 1] [3, 1] [3] [3] // 添加一个1，剩余[2, 2, 2] --------------------------------- [3, 1] [3, 1] [3, 2] [3] // 添加一个2，剩余[2, 2] --------------------------------- [3, 1] [3, 1] [3, 2] [3, 2] // 添加一个2，剩余[2] --------------------------------- [3, 1, 2] [3, 1] [3, 2] [3, 2] // 添加一个2，剩余[]
由于原数组已经排序，因此每一组的首尾两元素一定不是同一元素，这样我们可以安心将4个组合并到一起，保证其相邻元素不相同。
看下完整代码：
public int[] rearrangeBarcodes(int[] barcodes) {
Arrays.sort(barcodes); // 先排序
int[] map = new int[10001]; // 计算每个数出现的次数
int maxCount=0, num=0; // 定义最大次数和出现次数最多的数字
for(int i=0;i<barcodes.length;i++){
int count = ++map[barcodes[i]]; // 更新当前数字出现的次数
if(count > maxCount){ // 如果当前数字出现次数大于maxCount
maxCount = count; // 更新maxCount
num = barcodes[i]; // 更新出现次数最多的数字
}
}
List<List<Integer>> list = new ArrayList<>(); // 分组用list
for(int i=0;i<maxCount;i++){ // 按照最多次数分组
List<Integer> l = new ArrayList<>();
l.add(num); // 将出现次数最多的数字分别放进每一个组。
list.add(l);
}
int listIndex=0;
for(int i=0;i<barcodes.length;i++){ // 将剩余数字按顺序放入每一个组
if(barcodes[i]==num){
continue;
}
list.get(listIndex).add(barcodes[i]);
if(++listIndex == maxCount){
listIndex = 0;
}
}
int[] res = new int[barcodes.length]; // 定义返回值
int resIndex=0;
for(List<Integer> l: list){ // 将分组合并到一起
for(int n : l){
res[resIndex++]=n;
if(resIndex == barcodes.length){
return res;
}
}
}
return res;
}本解法执行时间为20ms。
Runtime: 20 ms, faster than 85.83% of Java online submissions for Distant Barcodes.
Memory Usage: 40.6 MB, less than 100.00% of Java online submissions for Distant Barcodes.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1054-distant-barcodes-解题思路分析/