本文主要是介绍力扣(距离相等的条形码),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1054. 距离相等的条形码
提示
在一个仓库里,有一排条形码,其中第 i
个条形码为 barcodes[i]
。
请你重新排列这些条形码,使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案,此题保证存在答案。
思路:
首先利用一个数组保存每个元素出现次数,即dp[i]表示i出现的次数。
然后先处理出现次数最多的元素,处理方法是从0开始,每隔两个存放一个该元素直到全部存完。
在处理完出现次数最多的元素后,对于其他元素,也是按照每间隔两个位置存放一个该元素的方法,当存放位置超过数组长度时,改为从1开始继续每间隔两个存放一个。最后就会得到所要求的数组。
重点是必须先存放出现次数最多的元素,极端情况下出现次数最多的元素可能是(n+1)/2个,此时相当于最后求出的数组,每间隔两个位置都有一个该元素,如果不先排该元素,则必定会在前面几个两两为一组的小组中没有一个该元素,则后面必定会出现该元素重复存放。(针对本方法来说!)。
对于出现的最大次数是(n+1)/2,是假设每两个相邻元素为一个小组,若没有重复,极端情况下是每个小组的第一个元素都是该元素,而最后一个小组可能只有一个元素,也可能有两个元素,因此是(n+1)/2.
class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {int n=0;for(auto e:barcodes){n=max(n,e);}vector<int>dp(n+1,0);for(auto e:barcodes){dp[e]++;}vector<int>ret(barcodes.size());//先处理最大的,其余随意int m=0;for(int i=0;i<dp.size();i++){if(dp[i]>dp[m]){m=i;}}int l=0;while(dp[m]){ret[l]=m;l+=2;dp[m]--;}for(int i=0;i<dp.size();i++){while(dp[i]){if(l>=ret.size()){l=0;}while(ret[l]!=0){l++;}ret[l]=i;dp[i]--;l+=2;}}return ret;}
};
这篇关于力扣(距离相等的条形码)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!