【LeetCode刷题集】--排序（四）

用户11915063

发布于 2025-11-20 09:25:06

580

题目一：三个数的最大乘积

题目链接：

628.三个数的最大乘积-力扣（LeetCode）

题意：

一个整型数组，要求你找出三个数乘积最大

思路：

qsort将数组从小到大排序，由于数组中可能存在负数的情况，所以我们可以求数组前两位的积，如果前两位都为负数，那么乘积就为整数，再乘上数组最后一个元素，由于从小到大排序，所以最后三位元素一定是最大的，但是不能保证乘积最大，所以我们可以再求一下最后三位的乘积，来求这两个值的最大值

代码实现：

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}
int maximumProduct(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    return fmax(nums[0] * nums[1] * nums[numsSize - 1], nums[numsSize - 3] * nums[numsSize - 2] * nums[numsSize - 1]);
}

复杂度分析：

时间复杂度：O(n*logn)

题目二：错误的集合

题目链接：

645.错误的集合-力扣（LeetCode）

题意：

一个数组包含了1-n的整数，由于数据错误导致一个数字复制了另一个数字，此时数组里又两个数字一样，从而缺少了它本身应该正确的数字，要求返回重复的整数和丢失的整数，以数组的形式返回

思路：

方法一：排序将数组排序之后，比较每对相邻的元素，即可找到错误的集合。寻找重复的数字较为简单，如果相邻的两个元素相等，则该元素为重复的数字。寻找丢失的数字相对复杂，可能有以下两种情况：

如果丢失的数字大于 1 且小于 n，则一定存在相邻的两个元素的差等于 2，这两个元素之间的值即为丢失的数字；
如果丢失的数字是 1 或 n，则需要另外判断。

为了寻找丢失的数字，需要在遍历已排序数组的同时记录上一个元素，然后计算当前元素与上一个元素的差。考虑到丢失的数字可能是 1，因此需要将上一个元素初始化为 0。

当丢失的数字小于 n 时，通过计算当前元素与上一个元素的差，即可得到丢失的数字；
如果 nums[n−1]=n，则丢失的数字是 n。

代码实现：

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int* findErrorNums(int* nums, int numsSize, int* returnSize) {
    int* errorNums = malloc(sizeof(int) * 2);
    *returnSize = 2;
    qsort(nums, numsSize, sizeof(int), cmp);
    int prev = 0;
    for (int i = 0; i < numsSize; i++) {
        int curr = nums[i];
        if (curr == prev) {
            errorNums[0] = curr;
        } else if (curr - prev > 1) {
            errorNums[1] = prev + 1;
        }
        prev = curr;
    }
    if (nums[numsSize - 1] != numsSize) {
        errorNums[1] = numsSize;
    }
    return errorNums;
}

复杂度分析：

时间复杂度：O(n*logn)

题目三：至少是其他数字两倍的最大数

题目链接：

747.只少是其他数字两倍的最大数

题意：

数组中存在唯一最大整数，判断它是否为其他数字的两倍，如果是返回最大数的下标，如果不是返回-1

思路：

遍历数组分别找到数组的最大值 m1和次大值 m2。如果 m1≥m2×2 成立，则最大值至少是数组其余数字的两倍，此时返回最大值的下标，否则返回 −1。为了返回最大值的下标，我们需要在计算最大值的同时记录最大值的下标。

代码实现：

int dominantIndex(int* nums, int numsSize) {
    int m1 = -1, m2 = -1;
    int index = -1;
    for (int i = 0; i < numsSize; i++) 
    {
        if (nums[i] > m1)//找最大值
        {
            m2=m1;
            m1 = nums[i];
            index = i;//记录最大值的下标
        } 
        else if (nums[i] > m2)//找次最大值
        {
            m2 = nums[i];
        }
    }
    return m1 >= m2 * 2 ? index : -1;
}