[1122] Relative Sort Array

竟然又PASS了！真是不可思議  XD

看起來別人有更漂亮的寫法？！（thinking 圖）

先把原本解法貼一下～之後再想XD

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int comp(const void *a, const void *b)

{

return *(int *)a - *(int*)b;

}

int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize){

int *idxArr2 = calloc (1001, sizeof(int));

int *count = calloc (arr2Size, sizeof(int));

int *ret = calloc (arr1Size, sizeof(int));

int retIdx=0;

for (int i=0;i <1001; i++) //初始值

idxArr2[i] = -1;

for (int i=0;i <arr2Size;i++) //紀錄arr2 val 的index

idxArr2[arr2[i]] = i;

for (int i=0;i<arr1Size;i++)

{

if ( idxArr2[arr1[i]] >= 0)

count[idxArr2[arr1[i]]]++;

else

ret[retIdx++]=arr1[i];

}

if (retIdx>1)

qsort(ret,retIdx, sizeof(int), comp);

int k=0;

for (int i=0;i<arr1Size; i++)

{

for (int j=0;j<arr2Size; j++)

{

while (count[j]>0)

{

arr1[i++]=arr2[j];

count[j]--;

}

}

if (retIdx > 0)

arr1[i]= ret[k++];

}

*returnSize = arr1Size;

return arr1;

}