刷题 ------ 排序

基于上篇的排序算法，本篇刷了一下leetcode上的关于排序算法的题，因为我是点的排序标签刷的，所以有些题排完序答案就出来了，就没有写题解了。

1.K 次取返后最大化的数组和（堆）

看完题目，首先得知道的就是，我们应该尽量把全部的负数去取反，因为最小的负数取反之后就会很大，所以到全部的负数都取反，不能再取之后，或者说是k次取完了。

• 如果k次取完了，那正好，直接返回当前数组的和就好了.
• 如果负数变更完了，k 还有偶数次，负负得正 所以你就可以一直取同样的一个数，所以还是可以返回当前数组的和就好了。
• 但是还有有一种情况，就是说，负数变更完了，而k是奇数次，变更那个最小的数就好了。

int cmp_int(const void* x, const void* y)
{
    return *(int*)x - *(int*)y;
}

int largestSumAfterKNegations(int* nums, int numsSize, int k)
{
    qsort(nums,numsSize,sizeof(int),cmp_int);
    int i = 0, sum = 0;
    //先将负数全部反正
    while(i < numsSize && k > 0 && nums[i] <= 0)
    {
        nums[i] = -nums[i];
        i++;
        k--;
    }
    //判断剩下的k是否为奇数。
    if(k % 2 != 0)
    {
        //再排序
        qsort(nums,numsSize,sizeof(int),cmp_int);
        nums[0] = -nums[0];
    }
    for (i = 0; i < numsSize; i++)
    {   
        sum += nums[i];
    }

    return sum;
}

还有一种思路是：选出最小的那一个数据，然后取反，之后接着选最小的数据，直到k次全部完毕。

• 可以用选择排序的方法，每次进行选择。
• 还可以建立一个小顶堆出来，然后将堆顶的数据去反后，再维护此堆。

void Swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void Heapify(int* nums, int numsSize, int i)
{
    int minIndx = i, lc = i * 2 + 1, rc = i * 2 + 2;
    if(lc < numsSize && nums[lc] < nums[minIndx])
    {
        minIndx = lc;
    }
    if(rc < numsSize && nums[rc] < nums[minIndx])
    {
        minIndx = rc;
    }
    if(minIndx != i)
    {
        Swap(&nums[i],&nums[minIndx]);
        Heapify(nums,numsSize,minIndx);
    }
}


int largestSumAfterKNegations(int* nums, int numsSize, int k)
{
    int i,sum = 0;
    //创建一个小顶堆
    for (i = (numsSize - 1) / 2; i >= 0; i--)
    {
        Heapify(nums,numsSize,i);
    }
    while(k > 0)
    {
        //将最小值拿出来后取反
        nums[0] = -nums[0]; 
        //维护堆,""
        Heapify(nums,numsSize,0);
        k--;
    }
    for (i = 0; i < numsSize; i++)
    {
        sum += nums[i];
    }

    return sum;
}

2.数组的相对排序（桶）

这道题可以用桶排序来做。

• 首先把arr1中所有出现的数字按照放入桶（哈希表）中。
• 然后遍历arr2中的对应的元素，放入ans中，即实现以arr2的形式排序arr1
• 最后将桶中还未取来的，依次放入ans中就好了。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
{
    int* bucket = (int*)calloc(1001,sizeof(int));
    int* ans = (int*)malloc(sizeof(int) * arr1Size);
    int size = 0,i,maxnum = 0;
    //桶排序
    for (i = 0; i < arr1Size; i++)
    {
        bucket[arr1[i]]++;
        if(maxnum < arr1[i])
        {
            maxnum = arr1[i];
        }
    }
    //按照arr2的顺序取出
    for (i = 0; i < arr2Size; i++)
    {
        while(bucket[arr2[i]] != 0)
        {
            ans[size++] = arr2[i];
            bucket[arr2[i]]--;
        }
    }
    
    //将arr1中剩余的按照升序放入ans中
    for (i = 0; i <= maxnum; i++)
    {
        while(bucket[i] >= 1)
        {
            ans[size++] = i;
            bucket[i]--;
        }
    }
    *returnSize = size;
    return ans;
}

3.最小绝对差

这道题就是让我们首先知道最小绝对差是多少，然后选出是最小绝对差的两个下标就好了。

• 首先给数组排序，相邻两个数的绝对差肯定是小的。
• 然后找处最小的。
• 最后再遍历一遍，选出符合最小绝对差的下标。

int cmp_int(const void* x, const void* y)
{
    return *(int*)x - *(int*)y;
}


int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes)
{
    int** ans = (int**)malloc(sizeof(int*) * (arrSize - 1));
    *returnColumnSizes = (int*)malloc(sizeof(int*) * (arrSize - 1));
    int i,gap,size = 0;
    for (i = 0; i < (arrSize - 1); i++)
    {
        ans[i] = (int*)malloc(sizeof(int) * 2);
        (*returnColumnSizes)[i] = 2;
    }
    qsort(arr,arrSize,sizeof(int),cmp_int);
    //求最小绝对差值
    gap = abs(arr[0] - arr[1]);
    for (i = 1; i < arrSize - 1; i++)
    {
        if(abs(arr[i] - arr[i+1]) < gap)
        {
            gap = abs(arr[i] - arr[i+1]);
        }
    }
    for (i = 0; i < arrSize - 1; i++)
    {
        if(abs(arr[i] - arr[i+1]) == gap)
        {
            ans[size][0] = arr[i];
            ans[size++][1] = arr[i+1];
        }
    }
    *returnSize = size;
    return ans;
}

4.根据数字二进制下1的数目排序（qsort）

这道题，让我对qsort函数有了一个新的认知。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int GetBinaryDigitSum(int n)
{
    int* nums = (int*)malloc(sizeof(int) * 32);
    int size = 0;
    while(n != 0)
    {
        nums[size++] = n % 2;
        n /= 2;
    }   
    int i, sum = 0;
    for (i = 0; i < size; i++)
    {
        sum += nums[i];
    }

    return sum;
}

int cmp_sum(const void* x, const void* y)
{
    int numx = *(int*)x,numy = *(int*)y;
    //求出二进制1的位置
    int c = GetBinaryDigitSum(numx),d = GetBinaryDigitSum(numy);
    //如果二进制1的位数相同，那么去利用原来数的大小去排序
    return c == d ? numx - numy : c - d;
}


int* sortByBits(int* arr, int arrSize, int* returnSize)
{
    qsort(arr,arrSize,sizeof(int),cmp_sum);
    *returnSize = arrSize;
    return arr;
}

5.有多少小于当前数字的数字

就对于每个数进行挨个求，直接用暴力就能解决，同业也可以用排序的方式来解决

• 首先需要将当前的这个数和下标存在一起，然后对数进行排序，这样子就会得到一个这样的数组
  
• 最后遍历data数组，用prev记录着上一个比自己小的数就好了.

int cmp_val(const void* x, const void* y)
{
    return ((int**)x)[0][0] - ((int**)y)[0][0];
}

int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize)
{
    //data 里面存放的是数据和下标
    int** data = (int**)malloc(sizeof(int*) * numsSize);
    int* ans = (int*)malloc(sizeof(int) * numsSize);
    *returnSize = numsSize;
    int i;
    for (i = 0; i < numsSize; i++)
    {
        data[i] = (int*)malloc(sizeof(int) * 2);
        data[i][0] = nums[i];
        data[i][1] = i;
    }

    //给data以val进行排序
    qsort(data,numsSize,sizeof(data),cmp_val);
    int prev = -1;
    for (i = 0; i < numsSize; i++)
    {
        if(i == 0 || data[i][0] != data[i-1][0])
        {
            prev = i;
        }
        ans[data[i][1]] = prev;
    }

    return ans;
}

6.非递增顺序的最小子序列

看完题之后，应该先排序，然后分别求出其前缀和与后缀和，拿当前数的后缀和与前一个数的前缀和去比较，像这个样子,

下面是代码：

• 所以我写的时候全部求出来了。官方题解，也就是这个意思，但是人家不用挨个全部求出来。
• 只要先计算出总共的和，然后从后往前遍历的时候本来就能算出后缀和，拿sum-后缀和，不就是前缀和吗？

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp_int(const void* x, const void* y)
{
    return *(int*)x - *(int*)y;
}

int* minSubsequence(int* nums, int numsSize, int* returnSize)
{
    int sum = 0;
    //先排序
    qsort(nums,numsSize,sizeof(int),cmp_int);
    int* ans = (int*)malloc(sizeof(int) * numsSize);
    int size = 0;
    int i,suffixsum = 0;
    for (i = 0; i < numsSize; i++)
    {
        sum += nums[i];
    }

    for (i = numsSize - 1; i >= 0; i--)
    {
        suffixsum += nums[i];
        ans[size++] = nums[i];
        if(sum - suffixsum < suffixsum)
        {
            break;
        }
    }

    *returnSize = size;
    return ans;
}

7.按照频率将数组升序排序（qsort）

优先考虑频率的排序，如果频率相同的话，再将其值按照降序的排序。

• 保证整个数组是有序，使重复的数在一起。
• 然后利用二维数组记录出每个数出现的次数。
• data[1][0] 表示1出现的次数
• data[1][1] 表示-1出现的次数
• 利用qsort对数组进行频率排序，频率相同的话，再将其值按照降序的排序.

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

#define ROW 101
#define COL 2

int data[ROW][COL];

int GetFreq(x)
{
    if(x >= 0)
    {
        return data[x][0];
    }
    else
    {
        return data[-x][1];
    }
}
 //按照频率排序
int cmp_freq(const void* x, const void* y)
{
    int numx = *(int*)x, numy = *(int*)y;
    int frex = GetFreq(numx), frey = GetFreq(numy);
    //如果频率相同，去比较值的大小。
    return frex == frey ? y - x : frex - frey;
}       

int cmp_int(const void* x, const void* y)
{
    return *(int*)x - *(int*)y;
}


int* frequencySort(int* nums, int numsSize, int* returnSize)
{
    int i,j;
    //重置二维数组
    for (i = 0; i < ROW; i++)
    {
        for (j = 0; j < COL; j++)
        {
            data[i][j] = 0;
        }
    }
    for (i = 0; i < numsSize; i++)
    {
        if(nums[i] >= 0)
        {
            //正数出现的次数
            data[nums[i]][0]++;
        }
        else
        {
            //负数出现的次数
            data[-nums[i]][1]++;
        }
    }
    qsort(nums,numsSize,sizeof(int),cmp_int);
    qsort(nums,numsSize,sizeof(int),cmp_freq);
    *returnSize = numsSize;
    return nums;
}

8.将句子排序

遍历一所给字符串，然后将其隐射到哈希中去。
就比如下图这个样子

• 然后整个哈希进行遍历，不为NULL依次放入ans中就好了

#define WORD_LEN 201

char * sortSentence(char * s)
{
    int i = 0,j = 0,len = strlen(s);
    char** words = (char**)malloc(sizeof(char*) * 11);
    char* ans = (char*)malloc(sizeof(char) * len);
    int pos = 0;
    for (i = 0; i < 11; i++)
    {
        words[i] = NULL;
    }
    //i记录起点
    i = 0;
    while(i < len)
    {
        //tmp 里面存放着单词
        char* tmp = (char*)malloc(sizeof(char) * WORD_LEN);
        //找数字
        while(j < len && !(s[j] >= '0' && s[j] <= '9'))
        {
            j++;
        }
        //在对应的索引处进行插入字符串
        int index = s[j] - '0';
        s[j] = '\0';
        strcpy(tmp,s + i);
        words[index] = tmp;
        //跳过空格
        j += 2;
        //i记录起点
        i = j;
    }

    //按照顺序拿出来就好了
    for (i = 0; i < 11; i++)
    {
        if(words[i] != NULL)
        {
            int size = strlen(words[i]);
            memcpy(ans + pos,words[i],sizeof(char) * size);
            pos += size;
            ans[pos++] = ' ';
        }
    }
    //调整最后一个字符
    ans[--pos] = '\0';
    return ans;
}

9.找到最大长度为 k 的子序列（双排序）

题目中不允许改变元素顺序，但是呢，要想得到最大的子序列，其子序列中的数据肯定还是原数组中最大的那几个数，于是我们可以排序两次，选出最大值后，再按照原来的顺序取回去就好了，如下图：

• 建立一个二维数组出来，data[i][0]放val data[i][1] 放其所对应的索引。
• 首先对二维数组data进行值的排序，选出k个最大的值。
• 再选出来的数组进行下标排序。[begin,numsSize].
• 最后拷贝到ans中就好了

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp_val(const void* x,const void* y)
{
    return ((int**)x)[0][0] - ((int**)y)[0][0];
}
int cmp_index(const void* x,const void* y)
{
    return ((int**)x)[0][1] - ((int**)y)[0][1];
}


int* maxSubsequence(int* nums, int numsSize, int k, int* returnSize)
{   
    if(numsSize == k)
    {
        *returnSize = k;    
        return nums;
    }
    int i;
    int** data = (int**)malloc(sizeof(int*) * numsSize);
    int* ans = (int*)malloc(sizeof(int) * k);
    int size = 0;
    for (i = 0; i < numsSize; i++)
    {
        data[i] = (int*)malloc(sizeof(int) * 2);
        data[i][0] = nums[i];
        data[i][1] = i;
    }
    //先按照值排序
    qsort(data,numsSize,sizeof(data[0]),cmp_val);
    int begin = numsSize - k;
    //再将选中的那些按照原先的位置排序[begin,k]
    qsort(data + begin,k,sizeof(data[0]),cmp_index);
    //拷贝即可[begin,numsSize]
    for (i = begin; i < numsSize; i++)
    {
        ans[size++] = data[i][0];
    }
    *returnSize = k;
    return ans;
}

10.对奇偶下标分别排序

• 构造两个数组，分别放偶数下标所对应的数，和奇数下标所对应的数。
• 然后将偶数数组升序排序，奇数数组降序排序
• 最后交叉放回数组中即可。

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

//升序
int Asc_cmp_int(const void* x,const void* y)
{
    return *(int*)x - *(int*)y;
}
//降序
int Des_cmp_int(const void* x,const void* y)
{
    return *(int*)y - *(int*)x;
}


int* sortEvenOdd(int* nums, int numsSize, int* returnSize)
{
    int* eveni = (int*)malloc(sizeof(int) * (numsSize / 2 + 1));
    int* oddi = (int*)malloc(sizeof(int) * (numsSize / 2 + 1));
    int i,eSize = 0,oSize = 0;
    for (i = 0; i < numsSize; i++)
    {
        if(i % 2 == 0)
        {
            eveni[eSize++] = nums[i];
        }
        else
        {
            oddi[oSize++] = nums[i];
        }
    }
    //偶数下标按照升序
    qsort(eveni,eSize,sizeof(int),Asc_cmp_int);
    //奇数下标按照降序
    qsort(oddi,oSize,sizeof(int),Des_cmp_int);
    int size = 0;
    for (i = 0; i < eSize; i++)
    {
        nums[size] = eveni[i];
        size += 2;
    }
    size = 1;
    for (i = 0; i < oSize; i++)
    {
        nums[size] = oddi[i];
        size += 2;
    }

    *returnSize = numsSize;
    return nums;
}
// 4 1 2 3

// 4  2 
// 1 3

// 2 4 
// 3 1
// 2 3 4 1

11. 按身高排序

这跟上面的9题是很类似的，同样也是利用一个二维数组，一个存身高，然后另一个存下标

• 看上面图中，先将身高按照降序排序，然后依次按找下标取字符串就好了.

int cmp_hight(const void* x, const void* y)
{
    return ((int**)y)[0][0] - ((int**)x)[0][0];
}


char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize)
{
    char** ans = (char**)malloc(sizeof(char*) * namesSize);
    int size = 0;
    int** data = (int**)malloc(sizeof(int*) * namesSize);
    int i;
    for (i = 0; i < namesSize; i++)
    {
        data[i] = (int*)malloc(sizeof(int) * 2);
        data[i][0] = heights[i];
        data[i][1] = i; //存放下标
    }
    qsort(data,namesSize,sizeof(data[0]),cmp_hight);

    for (i = 0; i < namesSize; i++)
    {
        ans[size++] = names[data[i][1]];
    }

    *returnSize = size;
    return ans;
}

12. 最小和分割

这道题，首先得知道一个理论把，就是一堆有序的数里面，将他平均分隔组成的两个数。
要想和最小，那么一定得是间隔的去取，就比如下图，是135 + 24

知道这一点，这道题就好办了。

void GetDigit(int* nums,int* size,int num)
{
    *size = 0;
    while(num != 0)
    {
        nums[(*size)++] = num % 10;
        num /= 10;
    }
}

int cmp_int(const void* x, const void* y)
{
    return *(int*)x - *(int*)y;
}

int splitNum(int num)
{
    int* nums = (int*)malloc(sizeof(int) * 10);
    int size = 0;
    GetDigit(nums,&size,num);
    qsort(nums,size,sizeof(nums[0]),cmp_int);
    int i, x = 0, y = 0;
    for (i = 0; i < size; i++)
    {
        if(i % 2 == 0)
        {
            x = x * 10 + nums[i];
        }
        else
        {
            y = y * 10 + nums[i];
        }
    }

    printf("x = %d ,y = %d \n",x,y);
    return x + y;
}

13.大于等于顺序前缀和的最小缺失整数

• 首先计算出顺序前缀和。
• 然后将数组中所有的数放入桶（哈希表中），同时求出最大值来。
• 如果前缀和大于最大值，说明前缀和肯定没有出现，如果小于取哈希表中查出现过没有，如果没出现过，返回整个前缀和就好了。
• 如果出现过，就在桶（哈希表）中从它的下一个位置去找，找到第一次未出现的数就是。

int missingInteger(int* nums, int numsSize)
{
    int* map = (int*)calloc(52,sizeof(int));
    int i,prefix = 0;
    //先求出顺序前缀
    for (i = 0; i < numsSize; i++)
    {
        prefix += nums[i];
        if(i+1 < numsSize && nums[i] + 1 != nums[i+1])
        {
            break;
        }
    }

    //统计每个数是否出现，同时求出最大值
    int max = 0;
    for (i = 0; i < numsSize; i++)
    {
        map[nums[i]] = 1;
        if(nums[i] > max)
        {
            max = nums[i];
        }
    }

    //如果说前缀和 比最大值都大，就证明里面肯定没有， || prefix 没有出现过
    if(prefix > max || map[prefix] == 0)
    {
        //满足条件直接返回就好了
        return prefix;
    }

    //说明prefix 出现在数组中，取找它的下一个没有出现过的。
    for (i = prefix + 1; i <= 52; i++)
    {
        if(map[i] == 0)
        {
            return i;
        }
    }

    return -1;
}

14.文物朝代判断

扑克牌？顺子？癞子？ 0 代表癞子？
这道题就是说给你个数组，数组里面的数字你随便排组合，如果能连起来就好了。

• 首先统计出癞子的个数（0的个数），然后再算出缺失数字的个数。
• 如果癞子的个数 >= 缺失的个数就能构成顺子。

int cmp_int(const void* x,const void* y)
{
    return *(int*)x - *(int*)y;
}

bool checkDynasty(int* places, int placesSize)
{
    qsort(places,placesSize,sizeof(int),cmp_int);
    int i = 0,zero = 0,miss = 0;
    //计算出0有多少个
    while(i < placesSize && places[i] == 0)
    {
        i++;
        zero++;
    }
    //去找缺失的数字的个数
    for (i; i < placesSize - 1; i++)
    {
        if(places[i+1] == places[i])
        {
            return false;
        }
        miss += places[i+1] - places[i] - 1;
    }
    return zero >= miss ? true : false;
}