石家庄网站建设推广公司,wordpress页面调用分类目录,做配资网站多少钱,电商类网站有哪些元素和最小的山形三元组
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件#xff0c;则认为它是一个 山形三元组 #xff1a;
i j knums[i] nums[j] 且 nums[k] nums[j]
请你找出 nums 中 元素和最小 的山形三元…元素和最小的山形三元组
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件则认为它是一个 山形三元组
i j knums[i] nums[j] 且 nums[k] nums[j]
请你找出 nums 中 元素和最小 的山形三元组并返回其 元素和 。如果不存在满足条件的三元组返回 -1 。 示例 1
输入nums [8,6,1,5,3]
输出9
解释三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组因为
- 2 3 4
- nums[2] nums[3] 且 nums[4] nums[3]
这个三元组的元素和等于 nums[2] nums[3] nums[4] 9 。可以证明不存在元素和小于 9 的山形三元组。示例 2
输入nums [5,4,8,7,10,2]
输出13
解释三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组因为
- 1 3 5
- nums[1] nums[3] 且 nums[5] nums[3]
这个三元组的元素和等于 nums[1] nums[3] nums[5] 13 。可以证明不存在元素和小于 13 的山形三元组。示例 3
输入nums [6,5,4,3,4,5]
输出-1
解释可以证明 nums 中不存在山形三元组。提示
3 nums.length 501 nums[i] 50 我的解答
思路先将整个数组从小到大排序以确保元素和最小在排序的过程中也将其一开始对应的下标改变顺序
再进行一下条件判断
i j knums[i] nums[j] 且 nums[k] nums[j]
第一次排序算法写错了出错 修改后提交依旧存在问题没法百分百通过
class Solution {public int minimumSum(int[] nums) {int lennums.length;int[] keynew int[len];int i0,j0,k0,temp0;for(i0;ilen;i){key[i]i;}for(i0;ilen-1;i){//冒泡排序for(j0;jlen-1-i;j){if(nums[j]nums[j1]){tempnums[j];nums[j]nums[j1];nums[j1]temp;tempkey[j];key[j]key[j1];key[j1]temp;}}}for(i0;ilen;i){for(j0;jlen;j){for(k0;klen;k){if(nums[i]nums[j]nums[k]nums[j]){if(key[i]key[j]key[j]key[k])return nums[i]nums[j]nums[k];}}}}return -1;}
} 官方题解
元素和最小的山形三元组 I 力扣官方题解
方法一枚举
思路与算法
我们直接按照题目的要求进行模拟枚举所有三元组即可。
class Solution {public int minimumSum(int[] nums) {int n nums.length, res 1000;for (int i 0; i n; i) {for (int j i 1; j n; j) {for (int k j 1; k n; k) {if (nums[i] nums[j] nums[k] nums[j]) {res Math.min(res, nums[i] nums[j] nums[k]);}}}}return res 1000 ? res : -1;}
}
复杂度分析
时间复杂度O(n3)O(n^3)O(n3)其中 nnn 是数组的长度。空间复杂度O(1)O(1)O(1)。
方法二数组
思路与算法
我们从左到右遍历来求出前缀数组中的最小值用 left[i]\textit{left}[i]left[i] 来表示前 iii 个数字的最小值。
然后我们从右到左遍历用 right\textit{right}right 来表示当前数字右边的最小值。 如果一个数比左右两边最小值大时说明找到一个山形三元组并更新当前山形三元组的最小元素和。
最后我们返回最小元素和即可。
class Solution {
public:int minimumSum(vectorint nums) {int n nums.size(), res 1000, mn 1000;vectorint left(n);for (int i 1; i n; i) {left[i] mn min(nums[i - 1], mn);}int right nums[n - 1];for (int i n - 2; i 0; i--) {if (left[i] nums[i] nums[i] right) {res min(res, left[i] nums[i] right);}right min(right, nums[i]);}return res 1000 ? res : -1;}
};复杂度分析
时间复杂度O(n)O(n)O(n)其中 nnn 是数组的长度。空间复杂度O(n)O(n)O(n)其中 nnn 是数组的长度。
