《六月集训》第三天——排序

• 前言
• 一、题目一
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 二、题目二
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 三、题目三
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 四、题目四
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 五、星球推荐

        
刷题坚持每一天，以下题目引用自：力扣（LeetCode）

原题链接：1464. 数组中两元素的最大乘积

        给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
        请你计算并返回该式的最大值。

示例 1：
输入：nums = [3,4,5,2]
输出：12
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)(nums[2]-1) = (4-1)(5-1) = 3*4 = 12

思路：

​         先递增排序，然后找最大值。

int cmp(const void* q1, const void* q2){
    return (*(int*)q1) - (*(int*)q2);
}
int maxProduct(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    return (nums[numsSize-1]-1)*(nums[numsSize-2]-1);
}

原题链接：1636. 按照频率将数组升序排序

        给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。
        请你返回排序后的数组。

示例 1：
输入：nums = [1,1,2,2,2,3]
输出：[3,1,1,2,2,2]
解释：‘3’ 频率为 1，‘1’ 频率为 2，‘2’ 频率为 3 。

思路：

​         用hash计数，根据计数量进行排序。

int hash[202];
int cmp(const void* q1, const void* q2){
    if(hash[*(int*)q1+100] == hash[*(int*)q2+100]) return *(int*)q2 - *(int*)q1;
    return hash[*(int*)q1+100] - hash[*(int*)q2+100];
}
int* frequencySort(int* nums, int numsSize, int* returnSize){
    memset(hash, 0, sizeof(hash));
    for(int i = 0; i < numsSize; ++i){
        ++hash[nums[i]+100];
    }
    qsort(nums, numsSize, sizeof(int), cmp);
    * returnSize = numsSize;
    return nums;
}

原题链接：1287. 有序数组中出现次数超过25%的元素

        给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
        请你找到并返回这个整数

示例 1：
输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6

思路：

​        因为是有序数组，所以直接计数判断是否超出25%。

int findSpecialInteger(int* arr, int arrSize){
    int count = 0;   
    for(int i = 1; i < arrSize; ++i){
        if(arr[i-1] == arr[i]){
            ++count;
            if(4*count > arrSize) return arr[i];
        } else count = 1;
    } 
    return arr[0];
}

原题链接：436. 寻找右区间

        给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。
        区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。
        返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

示例 1：
输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

思路：

​         先对区间按照 starte值 进行递增排序。然后判断在右边区间是否有 starte值 大于当前 end值 的区间，有则把索引，赋给ans。

int cmp(const int** q1, const int** q2){
    return (*q1)[0] - (*q2)[0];
}
int* findRightInterval(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize){
    * returnSize = intervalsSize;
    int* ans = (int*)malloc(sizeof(int)*intervalsSize);
    if(intervalsSize == 1){
        ans[0] = -1;
        return ans;
    }
    int** ret = (int**)malloc(sizeof(int*)*intervalsSize);
    for(int i = 0; i < intervalsSize; ++i){
        ret[i] = (int*)malloc(sizeof(int)*3);
        ret[i][0] = intervals[i][0];
        ret[i][1] = intervals[i][1];
        ret[i][2] = i;
    }
    qsort(ret, intervalsSize, sizeof(int*), cmp);
    //printf("%dn",ret[0][2]);
    for(int i = 0;i < intervalsSize; ++i){
        ans[ret[i][2]] = -1;
        for(int j = 0; j < intervalsSize; ++j){
            if(ret[i][1] <= ret[j][0]){
                ans[ret[i][2]] = ret[j][2];
                break;
            }
        }
    }
    return ans;
}

        星球链接：英雄算法联盟

星球里有什么?
        【朋友圈】一个极致精准的自律、编程、算法的小圈子。
        【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
        【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
        【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
        【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
        目前星球人数达到510+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。