|
| 1 | +##LeetCode第1054号问题：距离相等的条形码 |
| 2 | + |
| 3 | +>本文首发于公众号「图解面试算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。 |
| 4 | +> |
| 5 | +>同步个人博客：www.zhangxiaoshuai.fun |
| 6 | +
|
| 7 | +**本题选自leetcode第1054号问题，medium级别，目前通过率33.3%** |
| 8 | + |
| 9 | +**题目描述：** |
| 10 | + |
| 11 | +在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。 |
| 12 | +请你重新排列这些条形码，使其中两个相邻的条形码不能相等。 |
| 13 | +你可以返回任何满足该要求的答案，此题保证存在答案。 |
| 14 | +示例 1： |
| 15 | +输入：[1,1,1,2,2,2] |
| 16 | +输出：[2,1,2,1,2,1] |
| 17 | + |
| 18 | +示例 2： |
| 19 | +输入：[1,1,1,1,2,2,3,3] |
| 20 | +输出：[1,3,1,3,2,1,2,1] |
| 21 | + |
| 22 | +提示： |
| 23 | + 1 <= barcodes.length <= 10000 |
| 24 | + 1 <= barcodes[i] <= 10000 |
| 25 | +###题目分析： |
| 26 | +1.首先我们需要将每个条形码和出现的次数作一记录，为了存取方便，这里使用数组（题目中已经给出了数组的最大和最小长度）进行操作; |
| 27 | +2.找出其中出现最多次数的条形码，拿到该barcode和count; |
| 28 | +3.先将出现次数最多的条形码存入目标数组中（偶数位或者奇数位），并对记录数组作一更新； |
| 29 | +4.随后将剩余的barcode填充进目标数组中。 |
| 30 | + |
| 31 | +###GIF动画展示： |
| 32 | + |
| 33 | + |
| 34 | + |
| 35 | +###代码： |
| 36 | + |
| 37 | +```java |
| 38 | +publicstaticint[] rearrangeBarcodes(int[] barcodes){ |
| 39 | +int[] address=newint[10001]; |
| 40 | +for (int barcode: barcodes) |
| 41 | + address[barcode]++; |
| 42 | +// 找到出现次数最多的barcode |
| 43 | +int maxCode=0, maxCount=0; |
| 44 | +for (int i=0; i< address.length; i++) { |
| 45 | +if (maxCount< address[i]) { |
| 46 | + maxCode= i; |
| 47 | + maxCount= address[i]; |
| 48 | + } |
| 49 | + } |
| 50 | +int index=0; |
| 51 | +// 先填充最大的那一位barcode |
| 52 | +for (; address[maxCode]>0; index+=2) { |
| 53 | + barcodes[index]= maxCode; |
| 54 | + address[maxCode]--; |
| 55 | + } |
| 56 | +// 继续填充剩余的条形码 |
| 57 | +for (int i=1; i< address.length; i++) { |
| 58 | +while (address[i]>0) { |
| 59 | +//偶数位填充完毕 |
| 60 | +if (index>= barcodes.length) index=1; |
| 61 | + barcodes[index]= i; |
| 62 | + address[i]--; |
| 63 | + index+=2; |
| 64 | + } |
| 65 | + } |
| 66 | +return barcodes; |
| 67 | +} |
| 68 | +``` |