[2089] Find Target Indices After Sorting Array

拿來練習bubble sort的一題～

沒想到它居然還可以用一種叫做counting sort的方法！

就是說已經知道我要找的target是某個值，

那只要去算(1)比它小的數有幾個 跟(2) 它自己---也就是跟它一樣大的---有幾個，

這樣就可以算出index 了 ！！！amazing !!!

/**

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

*/

void swap(int *a, int*b)

{

int tmp;

tmp = *a;

*a=*b;

*b=tmp;

}

void BubbleSort(int* nums, int numsSize){

for (int j=numsSize-1;j>0;j--)

{

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

{

if (nums[i]>nums[i+1])

swap(&nums[i],&nums[i+1]);

}

}

}

int* targetIndices(int* nums, int numsSize, int target, int* returnSize){

BubbleSort(nums,numsSize);

int* ret = malloc(sizeof(int)*numsSize);

int count=0;

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

{

if (nums[i]==target)

{

ret[count++]=i;

}

if (nums[i]>target)

break;

}

*returnSize = count;

return ret;

}