Open azl397985856 opened 1 year ago
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
n = len(barcodes)
cnt = {}
for barcode in barcodes:
cnt[barcode] = cnt.get(barcode, 0) + 1
items = [(-val, key) for key, val in cnt.items()]
heapq.heapify(items)
cur = []
while items:
val, key = heapq.heappop(items)
cur += [key] * (-val)
j = 0
res = [0] * n
for i in range(0, n, 2):
res[i] = cur[j]
j += 1
for i in range(1, n, 2):
res[i] = cur[j]
j += 1
return res
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
int repeatsign;
sort(barcodes.begin(),barcodes.end());
vector<int> repeat,temp;
for(int i=0;i<barcodes.size()-1;i++){
if(barcodes[i+1]==barcodes[i]){
repeat.push_back(barcodes[i+1]);
barcodes.erase(barcodes.begin()+i+1);
i--;
}
}
temp=repeat;
while(temp.size()!=0){
if(temp.size()==1) {
barcodes.push_back(temp[0]);
return barcodes;
}
for(int i=0;i<temp.size();i++){
if(temp[i]==repeatsign) continue;
if(temp[i+1]!=temp[i]) {
barcodes.push_back(temp[i]);
temp.erase(temp.begin()+i);
i--;
continue;
}
else {
repeatsign=temp[i];
barcodes.push_back(temp[i]);
temp.erase(temp.begin()+i);
}
}
}
return barcodes;
}
};
class Solution: def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]: i, n = 0, len(barcodes) res = [0] * n for k, v in collections.Counter(barcodes).mostcommon(): for in range(v): res[i] = k i += 2 if i >= n: i = 1 return res
class Solution: def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]: n = len(barcodes) cnt = {} for barcode in barcodes: cnt[barcode] = cnt.get(barcode, 0) + 1 items = sorted([(-val, key) for key, val in cnt.items()])
cur = []
for val, key in items:
cur += [key] * (-val)
j = 0
res = [0] * n
for i in range(0, n, 2):
res[i] = cur[j]
j += 1
for i in range(1, n, 2):
res[i] = cur[j]
j += 1
return res
public int[] rearrangeBarcodes(int[] barcodes) {
if (barcodes == null || barcodes.length <= 1) return barcodes;
int[] cnt = new int[10_001];
for (int barcode : barcodes)
cnt[barcode]++;
var maxHeap = new PriorityQueue<Integer>(Comparator.comparingInt(i -> -cnt[i]));
for (int i = 0; i < cnt.length; i++) {
if (cnt[i] == 0) continue;
maxHeap.offer(i);
}
int n = barcodes.length;
int[] ans = new int[n];
int i = 0;
while (maxHeap.size() >= 2) {
var k1 = maxHeap.poll();
var k2 = maxHeap.poll();
cnt[k1]--;
cnt[k2]--;
ans[i] = k1;
ans[i + 1] = k2;
i += 2;
if (cnt[k1] > 0) maxHeap.offer(k1);
if (cnt[k2] > 0) maxHeap.offer(k2);
}
if (!maxHeap.isEmpty()) ans[i] = maxHeap.poll();
return ans;
}
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
int n = barcodes.length;
int[] cnt = new int[10001];
for(int barcode : barcodes){
cnt[barcode]++;
}
List<Integer> items = new ArrayList<>();
for(int i = 1; i < cnt.length; i++){
if(cnt[i] != 0){
items.add(i);
}
}
items.sort((o1, o2) -> cnt[o2] - cnt[o1]);
int[] cur = new int[n];
int j = 0;
for(int item : items){
for(int i = 0; i < cnt[item]; i++){
cur[j++] = item;
}
}
int[] res = new int[n];
j = 0;
for(int i = 0; i < n; i += 2){
res[i] = cur[j++];
}
for(int i = 1; i < n; i += 2){
res[i] = cur[j++];
}
return res;
}
}
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& b) {
priority_queue<pair<int, int>> q;
unordered_map<int,int> mp;
for(auto x: b){
mp[x]++;
}
for(const auto &[k, v]: mp) {
q.push({v, k});
}
vector<int> res;
while(q.size()) {
auto [v, k] = q.top(); q.pop();
if(res.empty() || res.back() != k) {
res.push_back(k);
if(--v) q.push({v, k});
}else{
if(q.size() < 1) return res;
auto [y, x] = q.top(); q.pop();
res.push_back(x);
if(--y) q.push({y, x});
q.push({v, k});
}
}
return res;
}
};
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
Map<Integer, Integer> counter = new HashMap<>();
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> (counter.get(y) - counter.get(x)));
for (int num : barcodes)
counter.put(num, counter.getOrDefault(num, 0) + 1);
for (int num : counter.keySet())
pq.offer(num);
int idx = 0;
while (pq.size() > 1) {
int first = pq.poll(), second = pq.poll();
barcodes[idx++] = first;
barcodes[idx++] = second;
counter.put(first, counter.get(first) - 1);
counter.put(second, counter.get(second) - 1);
if (counter.get(first) > 0)
pq.offer(first);
if (counter.get(second) > 0)
pq.offer(second);
}
if (pq.size() > 0)
barcodes[idx++] = pq.poll();
return barcodes;
}
}
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
unordered_map<int,int> m;
priority_queue<pair<int,int>> pq;
for(int b:barcodes){
m[b]++;
}
for(auto [k,v]:m){
pq.push({v,k});
}
int n=barcodes.size();
vector<int> ans(n,0);
int i=0;
while(pq.size()>1){
int f=pq.top().second;pq.pop();
int s=pq.top().second;pq.pop();
ans[i++]=f;
ans[i++]=s;
m[f]--;
m[s]--;
if(m[f]>0){
pq.push({m[f],f});
}
if(m[s]>0)pq.push({m[s],s});
// ans[i]=;
// pq.pop();
// i+=2;
// if(i>=n)i=1;
}
if(pq.size()>0)ans[i++]=pq.top().second;
return ans;
}
};
设:元素个数为N,不重复元素个数为K 时间复杂度: O(NlogK) 空间复杂度: O(K)
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
ans = []
n = len(barcodes)
while len(ans)!=n:
if len(barcodes)==1:
ans.append(barcodes[0])
break
record = {}
for num in barcodes:
record[num] = record.get(num, 0)+1
record = sorted(record.items(), key=lambda x: x[1], reverse=True)
for i in range(2):
ans.append(record[i][0])
barcodes.remove(record[i][0])
return ans
用堆排序出现的次数大小,岔开输出,先放次数多的。2个一组即可岔开。
/**
* @param {number[]} barcodes
* @return {number[]}
*/
var rearrangeBarcodes = function(barcodes) {
const map = {};
for(let i=0;i<barcodes.length;i++) {
map[barcodes[i]] = (map[barcodes[i]] ?? 0) + 1;
}
const maxQ = new MaxPriorityQueue({
priority: node => node.count
});
for(let key in map) {
maxQ.enqueue({
num: key,
count: map[key],
});
}
const res = [];
while(maxQ.size()>1) {
const first = maxQ.dequeue().element;
const second = maxQ.dequeue().element;
res.push(first.num);
res.push(second.num)
map[first.num] = first.count-1;
map[second.num] = second.count-1;
// 先放second,避免count相同,输出顺序相反
if (map[second.num] > 0) {
maxQ.enqueue({
num: second.num,
count: map[second.num],
});
}
if (map[first.num] > 0) {
maxQ.enqueue({
num: first.num,
count: map[first.num],
});
}
}
if (maxQ.size() > 0) {
res.push(maxQ.dequeue().element.num)
}
return res;
};
时间O(n*logk) 空间:O(k)
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
int size = barcodes.size();
unordered_map<int,int> map;
for(auto b : barcodes)
++map[b];
vector<pair<int,int>> slt;
for(auto it = map.begin(); it != map.end(); ++it)
slt.push_back({it -> first, it -> second});
sort(slt.begin(), slt.end(), [](pair<int,int> lhs, pair<int,int> rhs) {
return lhs.second > rhs.second;
});
int index = 0, res_index = 0;
while(index < slt.size())
barcodes[res_index] = slt[index].first;
res_index += 2;
--slt[index].second;
if(!slt[index].second) ++index;
if(res_index >= size) res_index = 1;
}
return barcodes;
}
};
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
int N = barcodes.length;
int[] freq = new int[10001];
int[] res = new int[N];
// 1. 记录 所有数字的 freq
for (int x : barcodes) {
freq[x]++;
}
// 2. 找到 出现次数最多的数 的 val 和 cnt
int maxVal = -1, maxCnt = -1;
for (int i = 0; i < 10001; i++) {
if (freq[i] > maxCnt) {
maxCnt = freq[i];
maxVal = i;
}
}
// 3. 填写答案, 把最大的都按隔一个填进去
int idx = 0;
for (int i = 0; i < maxCnt; i++) {
res[idx] = maxVal;
idx += 2;
}
freq[maxVal] = 0;
// 对于剩下所有的 freq, 按照 freq 的顺序, 一个隔一个填
for (int i = 0; i < 10001; i++) {
for (int j = 0; j < freq[i]; j++) {
if (idx >= N)
idx = 1;
res[idx] = i;
idx += 2;
}
}
return res;
}
}
1054. 距离相等的条形码
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/distant-barcodes/
前置知识
题目描述
请你重新排列这些条形码,使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案,此题保证存在答案。
示例 1:
输入:[1,1,1,2,2,2] 输出:[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