兰州网站建设加王道下拉,响应式网页设计技术,浙江省建设职业注册中心网站,数据库内容进 wordpress给你一个整型数组 nums #xff0c;在数组中找出由三个数组成的最大乘积#xff0c;并输出这个乘积。
我的答案#xff1a;#xff08;只通过了63个用例#xff0c;没考虑到两个负数相乘得正的情况#xff09;
class Solution {public int maximumProduct(int[] nums) …给你一个整型数组 nums 在数组中找出由三个数组成的最大乘积并输出这个乘积。
我的答案只通过了63个用例没考虑到两个负数相乘得正的情况
class Solution {public int maximumProduct(int[] nums) {Arrays.sort(nums);reverse(nums);return nums[0] * nums[1] * nums[2];}public void reverse(int[] nums) {int left 0, right nums.length - 1;while (left right) {int temp nums[left];nums[left] nums[right];nums[right] temp;left;right--;}}
}
看了题解改的答案
class Solution {public int maximumProduct(int[] nums) {Arrays.sort(nums);reverse(nums);int n nums.length;return Math.max(nums[0] * nums[1] * nums[2],nums[0] * nums[n-1] * nums[n-2]);}public void reverse(int[] nums) {int left 0, right nums.length - 1;while (left right) {int temp nums[left];nums[left] nums[right];nums[right] temp;left;right--;}}
} 官解 方法一排序 首先将数组排序。 如果数组中全是非负数则排序后最大的三个数相乘即为最大乘积如果全是非正数则最大的三个数相乘同样也为最大乘积。 如果数组中有正数有负数则最大乘积既可能是三个最大正数的乘积也可能是两个最小负数即绝对值最大与最大正数的乘积。 综上我们在给数组排序后分别求出三个最大正数的乘积以及两个最小负数与最大正数的乘积二者之间的最大值即为所求答案。 class Solution {public int maximumProduct(int[] nums) {Arrays.sort(nums);int n nums.length;return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);}
} 方法二线性扫描速度最快 在方法一中我们实际上只要求出数组中最大的三个数以及最小的两个数因此我们可以不用排序用线性扫描直接得出这五个数。 class Solution {public int maximumProduct(int[] nums) {// 最小的和第二小的int min1 Integer.MAX_VALUE, min2 Integer.MAX_VALUE;// 最大的、第二大的和第三大的int max1 Integer.MIN_VALUE, max2 Integer.MIN_VALUE, max3 Integer.MIN_VALUE;for (int x : nums) {if (x min1) {min2 min1;min1 x;} else if (x min2) {min2 x;}if (x max1) {max3 max2;max2 max1;max1 x;} else if (x max2) {max3 max2;max2 x;} else if (x max3) {max3 x;}}return Math.max(min1 * min2 * max1, max1 * max2 * max3);}
}
