b****p
发帖数: 216 | 1 今天在careercup上看到一个题目。Given an unordered array of positive integers
, create an algorithm that makes sure no group of integers of size bigger
than M have the same integers.
想到的死办法就是统计每个数字的个数之后放到一个heap里面去，每次取最大的一个，
要是连续取了M次了，就取第二大的。每次可以比较一下剩下的最大数目的数字k和所有
剩下来的元素n。 如果k比 n/(M+1)*M大的话就直接fail..
不知道还有什么好办法没有 | c******0
发帖数: 260 | 2 我不是很清楚LZ到底要怎么处理多出来的数字。我是把多余的数字跟最后一个数字交换
，然后数组大小减一。所以没有保障顺序。如果用vector,就可以直接删除。
int deleteExtra(int arr[], int size, int M){
unordered_map track;
int start = 0, end = M;
for(int i=0; i
track[ arr[i] ]++;
while(end < size){
if( track[ arr[end] ] == M){
swap( arr[end], arr[--size]);
}else{
track[ arr[start++] ]--;
track[ arr[end++] ]++;
}
}
for(int k=0; k
cout<
cout<
return size;
} | b****p
发帖数: 216 | 3 112222 m=2就不行了吧。
【在 c******0 的大作中提到】
: 我不是很清楚LZ到底要怎么处理多出来的数字。我是把多余的数字跟最后一个数字交换
: ，然后数组大小减一。所以没有保障顺序。如果用vector,就可以直接删除。
: int deleteExtra(int arr[], int size, int M){
: unordered_map track;
: int start = 0, end = M;
: for(int i=0; i: track[ arr[i] ]++;
:
: while(end < size){
: if( track[ arr[end] ] == M){
| x****g
发帖数: 1512 | 4 算法目标是啥？group数最少？
integers
【在 b****p 的大作中提到】
: 今天在careercup上看到一个题目。Given an unordered array of positive integers
: , create an algorithm that makes sure no group of integers of size bigger
: than M have the same integers.
: 想到的死办法就是统计每个数字的个数之后放到一个heap里面去，每次取最大的一个，
: 要是连续取了M次了，就取第二大的。每次可以比较一下剩下的最大数目的数字k和所有
: 剩下来的元素n。 如果k比 n/(M+1)*M大的话就直接fail..
: 不知道还有什么好办法没有
| c******0
发帖数: 260 | 5 我的输出时 1,1,2,2
不知道LZ想输出什么。。。
【在 b****p 的大作中提到】
: 112222 m=2就不行了吧。
|
|
