/**
* 算法思想：
* 关键是首先填满index为0,2,4,6,8等偶数的位置，然后剩余的元素填进空白处就行了。
*/
#define LEN 10001
typedef struct node{
int index;
int cnt;
} Node;
int cmp(Node *a, Node *b){
return a->cnt - b->cnt;
}
int* rearrangeBarcodes(int* arr, int len, int* returnSize){
Node ar[LEN];
int i,j=0;
int *ret = (int *)malloc(sizeof(int) * len);
int index = 0;
memset(ret, 0, sizeof(int) * len);
memset(ar, 0, sizeof(ar));
for(i=0; i<LEN; i++){
ar[i].index = i;
}
for(i=0; i<len; i++){
ar[arr[i]].cnt++;
}
qsort(ar, LEN, sizeof(Node), cmp);
for(i=LEN-1; i>=0; i--){
if(!ar[i].cnt) continue;
while(ar[i].cnt){
ret[j] = ar[i].index;
ar[i].cnt--;
j += 2;
if(j >= len) break;
}
if(j >= len) break;
}
for(i=LEN-1; i>=0; i--){
if(!ar[i].cnt) continue;
j = 0;
while(ar[i].cnt){
if(ret[j]){
j++;
if(j >= len) j=0;
}else{
ret[j] = ar[i].index;
ar[i].cnt--;
j += 1;
}
}
}
*returnSize = len;
for(i=0; i<index-1; i++){
if(ret[i] == ret[i+1]){
printf("err!, index = %d \n", i);
}
}
return ret;
}
