1054. Distant Barcodes

Problem

In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

Example 1:

Input: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

Input: [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,2,1,2,1]

Note:

1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

Problem Summary

In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i]. Please rearrange these barcodes so that no two adjacent barcodes are equal. You may return any answer that satisfies the requirement, and it is guaranteed that an answer exists.

Solution Approach

This problem uses exactly the same principle as Problem 767. Problem 767 is a Google interview question.
The solution approach is relatively simple: first sort by the frequency of each number in descending order, noting that there may be numbers with the same frequency. After sorting, take numbers starting from position 0 and from the middle position respectively; after all numbers are taken, the result is the final solution.

Code


package leetcode

import "sort"

func rearrangeBarcodes(barcodes []int) []int {
	bfs := barcodesFrequencySort(barcodes)
	if len(bfs) == 0 {
		return []int{}
	}
	res := []int{}
	j := (len(bfs)-1)/2 + 1
	for i := 0; i <= (len(bfs)-1)/2; i++ {
		res = append(res, bfs[i])
		if j < len(bfs) {
			res = append(res, bfs[j])
		}
		j++
	}
	return res
}

func barcodesFrequencySort(s []int) []int {
	if len(s) == 0 {
		return []int{}
	}
	sMap := map[int]int{}   // Count the frequency of each number
	cMap := map[int][]int{} // Sort using the frequency as the key
	for _, b := range s {
		sMap[b]++
	}
	for key, value := range sMap {
		cMap[value] = append(cMap[value], key)
	}
	var keys []int
	for k := range cMap {
		keys = append(keys, k)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(keys)))
	res := make([]int, 0)
	for _, k := range keys {
		for i := 0; i < len(cMap[k]); i++ {
			for j := 0; j < k; j++ {
				res = append(res, cMap[k][i])
			}
		}
	}
	return res
}