企业官网建设流程全解析

问题描述

在一次数学竞赛中，小C和小红被要求从一个整数数组中找出三个不同的数字，使得它们的乘积最大。但是有一个规则：这三个数字必须来自数组中的不同位置，且不能是同一个数字重复使用（即使数组中有重复数字，每个位置也只能用一次）。小C和小红需要合作设计一个高效的算法来解决这个问题，以便在竞赛中胜出。

要求：

1. 设计一个算法，时间复杂度为 O(n log n) 或更优，其中 n 是数组的长度。
2. 考虑数组可能包含正数、负数和零的情况，因为乘积的最大值可能由两个负数和一个正数相乘得到（例如，两个负数相乘为正，再乘以一个正数会更大）。

测试样例

样例1：

输入：nums = [1, 2, 3, 4]输出：24解释：最大的三个数字是 2, 3, 4，乘积为 2 * 3 * 4 = 24。

样例2：

输入：nums = [-10, -10, 1, 2, 3]输出：300解释：最大的乘积来自两个负数和一个正数：-10 * -10 * 3 = 300。

样例3：

输入：nums = [-1, -2, -3, -4]输出：-6解释：所有数字都是负数，乘积最大的是三个最大的负数（即绝对值最小的）：-1 * -2 * -3 = -6。

约束条件

• 3 ≤ nums.length ≤ 10^4
• -1000 ≤ nums[i] ≤ 1000
• 数组中的整数可以是正数、负数或零
• 保证至少存在三个不同的数字（但可能重复）

程序代码

#include <stdio.h>

#include <stdlib.h>

// 升序比较函数

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);

int n = numsSize;

// 情况1：最大的三个数

int p1 = nums[n-1] * nums[n-2] * nums[n-3];

// 情况2：两个最小的数 × 最大的数

int p2 = nums[0] * nums[1] * nums[n-1];

return p1 > p2 ? p1 : p2;

}

int main() {

int nums1[] = {1, 2, 3, 4};

int nums2[] = {-10, -10, 1, 2, 3};

int nums3[] = {-1, -2, -3, -4};

printf("%d\n", maximumProduct(nums1, 4)); // 24

printf("%d\n", maximumProduct(nums2, 5)); // 300

printf("%d\n", maximumProduct(nums3, 4)); // -6

return 0;

}

#include <stdio.h> #include <stdlib.h> // 升序比较函数 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); int n = numsSize; // 情况1：最大的三个数 int p1 = nums[n-1] * nums[n-2] * nums[n-3]; // 情况2：两个最小的数 × 最大的数 int p2 = nums[0] * nums[1] * nums[n-1]; return p1 > p2 ? p1 : p2; } int main() { int nums1[] = {1, 2, 3, 4}; int nums2[] = {-10, -10, 1, 2, 3}; int nums3[] = {-1, -2, -3, -4}; printf("%d\n", maximumProduct(nums1, 4)); // 24 printf("%d\n", maximumProduct(nums2, 5)); // 300 printf("%d\n", maximumProduct(nums3, 4)); // -6 return 0; }

运行结果