1054. Distant Barcodes

In a warehouse, there is a row of barcodes, where the ith 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: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

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

 

Constraints:

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

Rust Solution

struct Solution;
use std::collections::HashMap;

impl Solution {
    fn rearrange_barcodes(barcodes: Vec<i32>) -> Vec<i32> {
        let n = barcodes.len();
        if n == 1 {
            return barcodes;
        }
        let mut hm: HashMap<i32, usize> = HashMap::new();
        let mut max: (usize, i32) = (0, 0);
        for barcode in barcodes {
            let count = hm.entry(barcode).or_default();
            *count += 1;
            if *count > max.0 {
                max = (*count, barcode);
            }
        }
        let mut stack = vec![];
        for (k, v) in hm {
            if k != max.1 {
                for _ in 0..v {
                    stack.push(k);
                }
            }
        }
        for _ in 0..max.0 {
            stack.push(max.1);
        }
        let mut res = vec![0; n];
        let m = if n % 2 == 0 { n / 2 } else { (n + 1) / 2 };
        for i in 0..m {
            res[i * 2] = stack.pop().unwrap();
        }
        let mut i = 1;
        while let Some(top) = stack.pop() {
            res[i] = top;
            i += 2;
        }
        res
    }
}

#[test]
fn test() {
    let barcodes = vec![1, 1, 1, 2, 2, 2];
    let res = vec![1, 2, 1, 2, 1, 2];
    assert_eq!(Solution::rearrange_barcodes(barcodes), res);
    let barcodes = vec![1, 1, 2];
    let res = vec![1, 2, 1];
    assert_eq!(Solution::rearrange_barcodes(barcodes), res);
}

Having problems with this solution? Click here to submit an issue on github.