[C language brush leetcode] 1054. Bar code with equal distance (m)

【

In a warehouse , There is a row of bar codes , Among them the first i Barcodes are  barcodes[i].

Please rearrange these barcodes , So that any two adjacent barcodes cannot be equal . You can return any answer that meets this requirement , The answer to this question is guaranteed .

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,2,1,2,1]
 

Tips ：

1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/distant-barcodes
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

】

1.  When you see an array, first consider sorting , Sort by times , People think of hash

2.  No repetition , Then put even numbers first , Then put the odd position

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} UTHASH;

int Cmp(UTHASH *a, UTHASH *b) {
    return b->val - a->val;
}

int* rearrangeBarcodes(int* barcodes, int barcodesSize, int* returnSize){
    UTHASH *mymap = NULL;
    int i;
    int idx = 0;
    int *retarr = malloc(sizeof(int) * barcodesSize);

    for (i = 0; i < barcodesSize; i++) {
        UTHASH *find = NULL;
        HASH_FIND_INT(mymap, &barcodes[i], find);
        if (find != NULL) {
            find->val += 1;
        } else {
            UTHASH *new = malloc(sizeof(UTHASH));
            new->key = barcodes[i];
            new->val = 1;
            HASH_ADD_INT(mymap, key, new);
        }
    }

    HASH_SORT(mymap, Cmp);

    UTHASH *cur, *tmp;
    HASH_ITER(hh, mymap, cur, tmp) {    //  Traverse HASH surface 
        while (cur->val > 0) {          //  When the current element is not used up 
            retarr[idx] = cur->key;     //  Put the elements in retarr
            idx = idx + 2; // idx  Jump and put , That is, fill in the even digit first 
            if (idx >= barcodesSize) { //  If idx  arrive retarr The tail 
                idx = 1; //  Start filling in odd digits 
            }
            cur->val--; //  Put one element at a time , The number of elements minus one 
        }
    }

    *returnSize = barcodesSize;

    return retarr;
}

/*
1.  When you see an array, first consider sorting , Sort by times , People think of hash 
2.  No repetition , Then put even numbers first , Then put the odd position 
*/