Question

1054. Distant Barcodes

中文文档

Description

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

Solutions

Solution 1

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

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;
  }
}

class Solution {
public:
  vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    int mx = *max_element(barcodes.begin(), barcodes.end());
    int cnt[mx + 1];
    memset(cnt, 0, sizeof(cnt));
    for (int x : barcodes) {
      ++cnt[x];
    }
    sort(barcodes.begin(), barcodes.end(), [&](int a, int b) {
      return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
    });
    int n = barcodes.size();
    vector<int> ans(n);
    for (int k = 0, j = 0; k < 2; ++k) {
      for (int i = k; i < n; i += 2) {
        ans[i] = barcodes[j++];
      }
    }
    return ans;
  }
};

func rearrangeBarcodes(barcodes []int) []int {
  mx := slices.Max(barcodes)
  cnt := make([]int, mx+1)
  for _, x := range barcodes {
    cnt[x]++
  }
  sort.Slice(barcodes, func(i, j int) bool {
    a, b := barcodes[i], barcodes[j]
    if cnt[a] == cnt[b] {
      return a < b
    }
    return cnt[a] > cnt[b]
  })
  n := len(barcodes)
  ans := make([]int, n)
  for k, j := 0, 0; k < 2; k++ {
    for i := k; i < n; i, j = i+2, j+1 {
      ans[i] = barcodes[j]
    }
  }
  return ans
}

function rearrangeBarcodes(barcodes: number[]): number[] {
  const mx = Math.max(...barcodes);
  const cnt = Array(mx + 1).fill(0);
  for (const x of barcodes) {
    ++cnt[x];
  }
  barcodes.sort((a, b) => (cnt[a] === cnt[b] ? a - b : cnt[b] - cnt[a]));
  const n = barcodes.length;
  const ans = Array(n);
  for (let k = 0, j = 0; k < 2; ++k) {
    for (let i = k; i < n; i += 2, ++j) {
      ans[i] = barcodes[j];
    }
  }
  return ans;
}