LeetCode1054-距离相等的条形码

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/distant-barcodes/

中文链接：https://leetcode-cn.com/problems/distant-barcodes/

题目详述

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

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

示例 1：

1
2
输入：[1,1,1,2,2,2]
输出：[2,1,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 <= 10000
  • 1 <= barcodes[i] <= 10000

题目详解

  • 题目保证存在答案。
  • 可以按照这种贪心原则来安排顺序：统计每个数的出现次数，按照出现次数从大到小排序。然后用它们依次填充下标 0、2、4……位置，再填充下标 1、3、5……位置。
  • 时间复杂度为 O(nlogn)，时间主要花在排序上。
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
public class LeetCode_01054 {

    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : barcodes) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        Data[] ds = new Data[map.size()];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ds[i++] = new Data(entry.getKey(), entry.getValue());
        }
        Arrays.sort(ds);
        i = 0;
        for (Data d : ds) {
            while (d.cnt-- > 0) {
                barcodes[i] = d.x;
                i += 2;
                if (i >= barcodes.length) {
                    i = 1;
                }
            }
        }
        return barcodes;
    }

    class Data implements Comparable<Data> {
        int x, cnt;

        public Data(int x, int cnt) {
            this.x = x;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Data o) {
            return Integer.compare(o.cnt, cnt);
        }
    }
}
  • 实际上可以不用排序，只用把出现次数最多的数排好，其他的数的相对顺序可以是任意的。
  • 时间复杂度为 O(n)。
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
public class LeetCode_01054 {

    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : barcodes) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        Data[] ds = new Data[map.size()];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ds[i++] = new Data(entry.getKey(), entry.getValue());
        }
        Data data = Arrays.stream(ds).max(Comparator.comparingInt(o -> o.cnt)).get();
        i = 0;
        while (data.cnt-- > 0) {
            barcodes[i] = data.x;
            i += 2;
            if (i >= barcodes.length) {
                i = 1;
            }
        }
        for (Data d : ds) {
            if (d != data) {
                while (d.cnt-- > 0) {
                    barcodes[i] = d.x;
                    i += 2;
                    if (i >= barcodes.length) {
                        i = 1;
                    }
                }
            }
        }
        return barcodes;
    }

    class Data {
        int x, cnt;

        public Data(int x, int cnt) {
            this.x = x;
            this.cnt = cnt;
        }
    }
}