大型门户网站最担心的威胁是,网站建站软件,wordpress 订阅,东莞三合一网站建设原题链接#xff1a; 2908. 元素和最小的山形三元组 I - 力扣#xff08;LeetCode#xff09; 题目解读#xff1a; 给定一个整数数组nums#xff0c;如果下标i,j,k满足
ijknums[i]num[j]并且nums[k]num[j]
则称为山型三元组#xff0c;返回所有山型三…原题链接 2908. 元素和最小的山形三元组 I - 力扣LeetCode 题目解读 给定一个整数数组nums如果下标i,j,k满足
ijknums[i]num[j]并且nums[k]num[j]
则称为山型三元组返回所有山型三元组中nums[i]num[j]num[k]最小的值。如果没有山型三元组返回 -1
3 nums.length 501 nums[i] 50 解法一暴力遍历 对i,j,k 的组成的所有情况进行测试
class Solution {
public:int minimumSum(vectorint nums) {int size nums.size();int i, j, k;int ret INT_MAX;//三层暴力循环for (i 0; i size; i){for (j i 1; j size; j){for (k j 1; k size; k){//if判断为真的话为山型三元组if (nums[i] nums[j] nums[k] nums[j])ret min(ret, nums[i] nums[j] nums[k]);//如果新的三元组和大于ret更新ret的值}}}//如果retINT_MAX证明没有合法的三元组返回 -1if (ret INT_MAX)return -1;elsereturn ret;}
};
时间复杂度o(n^3)
空间复杂度o(1)
解法二前缀和后缀和 当ja时数组元素中只有从0下标到a-1下标的最小元素和从a1下标到n-1下标的最小元素是有意义的元素。在暴力解法中我们相当于是通过遍历i和k的所有情况来寻找这两个值遍历过程中进行了大量可避免的计算我们可以通过将不同下标对应的两个最小值提前求出来并存储在数组中来提高运行效率 Solution {
public:int minimumSum(vectorint nums) {const int size nums.size();int ret INT_MAX;//如果retINT_MAX证明没有合法的三元组返回 -1int left[55];int right[55];//left记录对于任意下标左侧的最小值left[0] nums[0];for (int i 1; i size - 1; i){left[i] min(nums[i - 1], left[i - 1]);}//right记录对于任意下标右侧的最小值right[size - 1] nums[size - 1];for (int i size - 2; i 0; i--){right[i] min(right[i 1], nums[i]);}for (int j 1; j size - 1; j){if (left[j] nums[j] right[j] nums[j])ret min(ret, nums[j] left[j] right[j]);} if (ret INT_MAX)return -1;elsereturn ret;}
};
时间复杂度o(n)
空间复杂度o(n) 对解法二的适当轻微优化
对于解法二来说可以看出生成left数组和循环j是十分相似的理论上来说他们是可以写在一起的向下面这样。 for (int j 1; j size - 1; j) { left[j] min(nums[j - 1], left[j - 1]); if (left[j] nums[j] right[j] nums[j]) ret min(ret, nums[j] left[j] right[j]); } 对于此时的left数组来说有意义的值只有left[j]和left[j-1]这两个值如果想想办法用两个单独的数来表示left[j]和left[j-1],就可以将一个数组优化为两个值。 其实left[j-1]可以看做left[j]的上一次的状态。我这边就用一个整数left来代替left数组。
class Solution {
public:int minimumSum(vectorint nums) {const int size nums.size();int ret INT_MAX;//如果retINT_MAX证明没有合法的三元组返回 -1int right[50];//right记录对于任意下标右侧的最小值right[size - 1] nums[size - 1];for (int i size - 2; i 0; i--){right[i] min(right[i 1], nums[i]);}//将left数组优化为l个元素int left 0;for (int j 1; j size - 1; j){if (nums[left] nums[j] right[j] nums[j])ret min(ret, nums[j] nums[left] right[j]);else if (nums[j] nums[left])left j;}if (ret INT_MAX)return -1;elsereturn ret;}
};
时间复杂度o(n)
空间复杂度o(n) 感谢观看
