java 解法, 执行用时: 35 ms, 内存消耗: 44.1 MB, 提交时间: 2023-05-14 16:56:47

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length;
        Integer[] t = new Integer[n];
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            t[i] = barcodes[i];
            mx = Math.max(mx, barcodes[i]);
        }
        int[] cnt = new int[mx + 1];
        for (int x : barcodes) {
            ++cnt[x];
        }
        Arrays.sort(t, (a, b) -> cnt[a] == cnt[b] ? a - b : cnt[b] - cnt[a]);
        int[] ans = new int[n];
        for (int k = 0, j = 0; k < 2; ++k) {
            for (int i = k; i < n; i += 2) {
                ans[i] = t[j++];
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 152 ms, 内存消耗: 18.8 MB, 提交时间: 2023-05-14 16:56:06

# 计数+排序
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        cnt = Counter(barcodes)
        barcodes.sort(key=lambda x: (-cnt[x], x))
        n = len(barcodes)
        ans = [0] * len(barcodes)
        ans[::2] = barcodes[: (n + 1) // 2]
        ans[1::2] = barcodes[(n + 1) // 2:]
        return ans

java 解法, 执行用时: 23 ms, 内存消耗: 44.3 MB, 提交时间: 2023-05-14 16:55:34

class Solution {
    public static int[] rearrangeBarcodes(int[] barcodes) {
        int length = barcodes.length;
        if (length < 2) {
            return barcodes;
        }

        Map<Integer, Integer> counts = new HashMap<>();
        int maxCount = 0;
        for (int b : barcodes) {
            counts.put(b, counts.getOrDefault(b, 0) + 1);
            maxCount = Math.max(maxCount, counts.get(b));
        }

        int evenIndex = 0;
        int oddIndex = 1;
        int halfLength = length / 2;
        int[] res = new int[length];
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int x = entry.getKey();
            int count = entry.getValue();
            while (count > 0 && count <= halfLength && oddIndex < length) {
                res[oddIndex] = x;
                count--;
                oddIndex += 2;
            }
            while (count > 0) {
                res[evenIndex] = x;
                count--;
                evenIndex += 2;
            }
        }
        return res;
    }
}

python3 解法, 执行用时: 144 ms, 内存消耗: 17.6 MB, 提交时间: 2023-05-14 16:55:10

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        length = len(barcodes)
        if length < 2:
            return barcodes

        counts = {}
        max_count = 0
        for b in barcodes:
            counts[b] = counts.get(b, 0) + 1
            max_count = max(max_count, counts[b])

        evenIndex = 0
        oddIndex = 1
        half_length = length // 2
        res = [0] * length
        for x, count in counts.items():
            while count > 0 and count <= half_length and oddIndex < length:
                res[oddIndex] = x
                count -= 1
                oddIndex += 2
            while count > 0:
                res[evenIndex] = x
                count -= 1
                evenIndex += 2
        return res

golang 解法, 执行用时: 60 ms, 内存消耗: 6.9 MB, 提交时间: 2023-05-14 16:54:52

func rearrangeBarcodes(barcodes []int) []int {
    if len(barcodes) < 2 {
        return barcodes
    }

    counts := make(map[int]int)
    maxCount := 0
    for _, b := range barcodes {
        counts[b] = counts[b] + 1
        if counts[b] > maxCount {
            maxCount = counts[b]
        }
    }

    evenIndex := 0
    oddIndex := 1
    halfLength := len(barcodes) / 2
    res := make([]int, len(barcodes))
    for x, count := range counts {
        for count > 0 && count <= halfLength && oddIndex < len(barcodes) {
            res[oddIndex] = x
            count--
            oddIndex += 2
        }
        for count > 0 {
            res[evenIndex] = x
            count--
            evenIndex += 2
        }
    }
    return res
}

golang 解法, 执行用时: 124 ms, 内存消耗: 7.2 MB, 提交时间: 2023-05-14 16:54:38

type PriorityQueue [][]int

func (pq PriorityQueue) Len() int {
    return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i][0] > pq[j][0]
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
    item := x.([]int)
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[:n-1]
    return item
}

func rearrangeBarcodes(barcodes []int) []int {
    count := make(map[int]int)
    for _, b := range barcodes {
        count[b]++
    }
    q := &PriorityQueue{}
    heap.Init(q)
    for k, v := range count {
        heap.Push(q, []int{v, k})
    }
    n := len(barcodes)
    res := make([]int, n)
    for i := 0; i < n; i++ {
        p := heap.Pop(q).([]int)
        cx, x := p[0], p[1]
        if i == 0 || res[i-1] != x {
            res[i] = x
            if cx > 1 {
                heap.Push(q, []int{cx - 1, x})
            }
        } else {
            p2 := heap.Pop(q).([]int)
            cy, y := p2[0], p2[1]
            res[i] = y
            if cy > 1 {
                heap.Push(q, []int{cy - 1, y})
            }
            heap.Push(q, []int{cx, x})
        }
    }
    return res
}

python3 解法, 执行用时: 184 ms, 内存消耗: 18.2 MB, 提交时间: 2023-05-14 16:54:23

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = Counter(barcodes)
        q = []
        for x, cx in count.items():
            heapq.heappush(q, (-cx, x))
        res = []
        while len(q) > 0:
            cx, x = heapq.heappop(q)
            if len(res) == 0 or res[-1] != x:
                res.append(x)
                if cx < -1:
                    heapq.heappush(q, (cx + 1, x))
            else:
                cy, y = heapq.heappop(q)
                res.append(y)
                if cy < -1:
                    heapq.heappush(q, (cy + 1, y))
                heapq.heappush(q, (cx, x))
        return res

java 解法, 执行用时: 40 ms, 内存消耗: 44.3 MB, 提交时间: 2023-05-14 16:54:09

// 最大堆
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int b : barcodes) {
            if (!count.containsKey(b)) {
                count.put(b, 0);
            }
            count.put(b, count.get(b) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            pq.offer(new int[]{entry.getValue(), entry.getKey()});
        }
        int n = barcodes.length;
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            int[] p = pq.poll();
            int cx = p[0], x = p[1];
            if (i == 0 || res[i - 1] != x) {
                res[i] = x;
                if (cx > 1) {
                    pq.offer(new int[]{cx - 1, x});
                }
            } else {
                int[] p2 = pq.poll();
                int cy = p2[0], y = p2[1];
                res[i] = y;
                if (cy > 1) {
                    pq.offer(new int[]{cy - 1, y});
                }
                pq.offer(new int[]{cx, x});
            }
        }
        return res;
    }
}