文章目录
前言
为了结束假期的无效刷题，有幸参与了 高校算法学习社区的七月暑期刷题营，能和大佬们一起学习进步是一种幸福。不多说直接开始今天的算法习题之旅…
一、三个数的最大乘积
题目描述
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
解题思路
1.先排序根据情况找出最大乘积
首先将数组排序。
排序过后分为三种情况：
- 如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积
- 如果全是非正数，则最大的三个数相乘同样也为最大乘积
- 如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积
综上，我们在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。
2.直接找出我们需要的数值进行相乘比较（线性扫描）
通过思路一可以得出，无论怎么样我们所需要的无非就是五个数据：最大的三个数和最小的两个数，那么我们需要做的就是通过一次扫描找出这五个数保存下来，分别乘积比较。
代码：思路1
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]); } }
代码：思路2
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 (min1 * min2 * max1) > (max1 * max2 * max3) ? (min1 * min2 * max1) : (max1 * max2 * max3); } }
二、有多少小于当前数字的数字
题目描述
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/how-many-numbers-are-smaller-than-the-current-number
解题思路
1.嵌套两次遍历数组得出结果
首先创建一个相同长度的数组，通过两次遍历得出想要的结果
本思路就属于暴力破解了，自然时间复杂度相对较大
2.排序
排序应该是第二个自然想到的方法了吧将数组排序，并记录每一个数在原数组中的位置（不然最后的结果就不知道放在哪里了）。排序后的数组中的每一个数，我们找出其左侧第一个小于它的数，这样就能够知道数组中小于该数的数量
3.计数排序
这个思路就比较新奇了，小编也没有想到（可能见的比较少），一起来看看吧。感兴趣的小伙伴可以一起研究研究。这个的代码就不在写上了哦。
注意到数组元素的值域为[0,100]，所以可以考虑建立一个频次数组 cntcnt ，cnt[i]cnt[i] 表示数字 ii 出现的次数。那么对于数字 ii 而言，小于它的数目就为 cnt[0…i-1]cnt[0…i−1] 的总和。
作者：LeetCode-Solution
来源：力扣（LeetCode）
代码：思路一
class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int[] res = new int[nums.length]; for(int i = 0 ; i < nums.length; i++){ int count = 0; for(int j = 0 ; j < nums.length ; j++){ if(j == i ) continue; if(nums[j] != nums[i] && nums[j] < nums[i]) count++; } res[i] = count; } return res; } }
代码：思路二
class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int n = nums.length; int[][] data = new int[n][2]; for (int i = 0; i < n; i++) { data[i][0] = nums[i]; data[i][1] = i; } Arrays.sort(data, new Comparator<int[]>() { public int compare(int[] data1, int[] data2) { return data1[0] - data2[0]; } }); int[] ret = new int[n]; int prev = -1; for (int i = 0; i < n; i++) { if (prev == -1 || data[i][0] != data[i - 1][0]) { prev = i; } ret[data[i][1]] = prev; } return ret; } }
总结
今天的算法题有些难度，有些题目只能想到暴力破解方法，自然这也是大多是小伙伴的思路，写完看看大佬们的更优解学习一下，这不也是很好的习惯吗。
😎重在坚持，继续努力。喜欢的小伙伴欢迎一键三连哦。😎
The man who fears losing has aleardy lost.
怕输的人已经输了。
-《权力的游戏》
