1. 距离相等的条形码 - Distant Barcodes

【桶排序?】

Problem Link

在一个仓库里,有一排条形码,其中第 i 个条形码为 barcodes[i]

请你重新排列这些条形码,使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案,此题保证存在答案。

Example:

示例 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. 1 <= barcodes.length <= 10000
  2. 1 <= barcodes[i] <= 10000

Analysis

为了保证可以实现相邻一定不相等,可以依次交错排列同一个数字。

  • 首先统计每个数字的出现次数

最特殊的情况为,数组的长度为奇数,某一个数字出现 $(length+1)/2$ 次, 如 [2, 1, 2, 1, 2],此时必须先从奇数位开始放置2,之后才能防止别的数组。

  • 首先从奇数位开始放置出现次数最多的数字。
  • 将其余数字放置在奇数位。
  • 将剩余数字依次放置在偶数位。

Solution ( 9ms)

执行用时 : 9 ms, 在Distant Barcodes的Java提交中击败了100.00% 的用户

内存消耗 : 51.9 MB, 在Distant Barcodes的Java提交中击败了100.00% 的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        /* 存在特殊情况结果类似 2, 1, 2, 1, 2
         * 因此优先使用出现次数最多的元素填充奇数位
         */
        /* 统计每个数据的出现次数 */
        int len = barcodes.length;
        int[] count = new int[10001];
        for (int i = 0; i < len; i++) {
            count[barcodes[i]]++;
        }       
        /* 得到出现次数最多的数字 */
        int maxCnt = 0;
        int maxNum = 0;
        for (int i = 1; i < 10001; i++) {
            if (count[i] > maxCnt) {
                maxCnt = count[i];
                maxNum = i;
            }
        }
        /* 先填充奇数位 */
        int[] result = new int[len];
        int pos = 0;    // result 填充位置
        int idx = 0;    // count 使用位置
        /* 先使用出现次数最多的数字填充奇数位, 最多恰好填满 */
        while (pos < len) {
            if (count[maxNum] <= 0) {
                break;  // 填充完毕
            } else {
                count[maxNum]--;
                result[pos] = maxNum;
                pos += 2;
            }
        }
        /* 尝试继续填充奇数位 */
        while (pos < len) {
            if (count[idx] <= 0) {
                idx++;
                continue;
            } else {
                count[idx]--;
                result[pos] = idx;
                pos += 2;
            }
        }
        /* 继续填充偶数位 */
        pos = 1;
        while (pos < len) {
            if (count[idx] <= 0) {
                idx++;
                continue;
            } else {
                count[idx]--;
                result[pos] = idx;
                pos += 2;
            }
        }
        return result;
        
    }
}

复杂度分析

可以优化统计的方式,降低为 O(N)

时间:10001 * x

空间:10001 * x