建设工程教育网官方网站,0网站建设公司宣传册,app网站设计制作,免费ppt模板下载应用java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 排序选择线性搜索最值 排序
解题思路#xff1a;时间复杂度O( …java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 排序选择线性搜索最值 排序
解题思路时间复杂度O( n ∗ l o g 2 n n*log_2n n∗log2n)空间复杂度O( l o g 2 n log_2n log2n)时间和空间复杂度都用在了快速排序上 对于一堆数里面挑出3个乘积最大是个数学问题有3种情况 这些数都是正数则最大的3个数乘积最大这些数都是负数则最大的3个数乘积最大有正有负则可能是两个最小的和一个最大的乘积最大也可能是3个最大的数乘积最大 只有1个正数则最小的两个负数和这个正数相乘乘积最大有多个正数也有可能两个最小负数和最大正数更大。例如有[-20000,-10000,1,2,3]这样的数组,最大乘积为 − 10000 ∗ − 20000 ∗ 3 -10000*-20000*3 −10000∗−20000∗3 综上所述我们只需要找出3个最大的数已经2个最小的数。然后取两种方案中大的即可。 3个最大的数乘积可能是最大没有负数或者负数乘积都特别小的情况2个最小加最大的数可能是最大2个特别小的负数一个最大正数 有了上面的分析我们的问题就变成了找到数组中最大的3个数和最小的2个数 先排序然后直接得到快速查找算法找到对应数字线性搜索找最值 代码这里是先排序的思路 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]);}
}选择
解题思路时间复杂度O( n n n)空间复杂度O( l o g 2 n log_2n log2n) 法一使用快速排序做而对于仅仅找特定几个值的话快速选择时间复杂度更低对于找到第几大的值可以参考215题 LeetCode215. 数组中的第K个最大元素https://blog.csdn.net/grd_java/article/details/136932454
代码 class Solution {public int maximumProduct(int[] nums) {int n nums.length;int min1 quickSort(nums,0,n-1,1),min2 quickSort(nums,0,n-1,2);int max1 quickSort(nums,0,n-1,n);int max2 quickSort(nums,0,n-1,n-1);int max3 quickSort(nums,0,n-1,n-2);return Math.max(max1*min1*min2, max1*max2*max3);}int quickSort(int[] a, int left,int right,int k){if(left right) return a[left];int x a[left right 1];//获取当前区间中间的数x//借助两个下标让比x小的去x左边比x大的去右边int leftIndex left - 1, rightIndex right 1;//分别代表区间中应该在x左边x的下标和x右边的下标while(leftIndex rightIndex){do leftIndex;while(a[leftIndex] x);//当leftIndex指向的值x时终止循环do rightIndex--;while(a[rightIndex] x);//当rightIndex指向的值x时终止循环if(leftIndex rightIndex){//如果leftIndex目前在x左边而且rightIndex目前在x右边说明他俩的指向的值应该调换位置swap(a,leftIndex,rightIndex);//让小的去x左边leftIndex位置大的去x右边rightIndex位置}}//直到目前区间实现x是中位数左边都比x小右边都比x大为止//此时rightIndex必然指向第一个比x小的值也就是x比它小的左边部分的边界if(k (rightIndex - left 1)) //如果left到rightIndex区间比x小的左边部分正好够我们找到第k大数return quickSort(a,left,rightIndex,k);//进入左边区间继续寻找else //如果左边部分没有第k大数那就去右边找此时左边部分的 rightIndex - left 1已经确定都比第k大数小所以k - 左边部分为下轮右边部分该找的值return quickSort(a,rightIndex1,right,k-(rightIndex-left1));//右边部分找第(k - 左边部分个数)大的数。}void swap(int[] a,int i,int j){int t a[i];a[i] a[j];a[j] t;}
}线性搜索最值
解题思路时间复杂度O( n n n)空间复杂度O( 1 1 1) 对于一个数组的最大值和最小值或者第二大第2小等等。只要我们找的是边缘值100个数找最小的3个找最大的3个线性搜索效率会更高。但是如果是100个数里面找排序后最小的27个数肯定不如快速选择和小根堆。对于只找很少量的几个最值线性搜索会很方便只需要遍历一次数组 代码可见线性搜索找最大的3个值就要3个if100个就要100个if所以只有找少数几个最值的时候可用 class Solution {public int maximumProduct(int[] nums) {//最大的3个int max1 Integer.MIN_VALUE, max2 Integer.MIN_VALUE, max3 Integer.MIN_VALUE;//最小的两个int min1 Integer.MAX_VALUE, min2 Integer.MAX_VALUE;//线性搜索for (int num : nums) {if (num max3) {//如果当前值第3大max3if (num max2) max3 num;//小于第二大max2就赋值给max3else if (num max1) {//大于max2小于max1max2的值给max3num赋值给max2max3 max2;//max2的值变为第3大max2 num;//num变为第二大} else {//如果也大于max1max3 max2;//max2给max3max2 max1;//max1给max2max1 num;//num给max1}}//如果当前值小于min2if (num min2) {if (num min1) min2 num;//但是大于min1则num给min2else {//如果小于min1min2 min1;//min1给min2min1 num;//num给min1}}}//可见线性搜索找最大的3个值就要3个if100个就要100个if所以只有找少数几个最值的时候可用//两种方案返回大的return Math.max(max1 * max2 * max3, max1 * min1 * min2);}
}
