主页 / coding / 问题 / 79173229
Accepted
kace91
Asked: 2024-11-10 00:38:53 +0800 CST

增加三重子序列 - 这个解决方案真的有效吗？为什么？

  • 772

我一直在努力解决 LeetCode 问题334。增加三元组子序列：

给定一个整数数组nums，返回true 是否存在一个三元组索引 (i, j, k) 使得 i < j < k和nums[i] < nums[j] < nums[k]。如果不存在这样的索引，则返回false。

[...]

跟进：您能否实现一个时间复杂度为 O（n），空间复杂度为 O（1）的解决方案？

因此数字不需要连续，但它们的索引需要排序；也就是说，[1,2,0,3]由于有效所以为真[1,2,3]，但[3,2,1]为假。

在找到足够好的解决方案并通过测试并阅读已接受的解决方案后，我发现公认的最有效的解决方案是这样的：

var increasingTriplet = function (nums) {
    let a = Infinity, b = Infinity, c = Infinity;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] <= a) a = nums[i];
        else if (nums[i] <= b) b = nums[i];
        else if (nums[i] <= c) {
            return true;
        }        
    }
    return false;
}

虽然它确实通过了测试用例，但我不确定它是否正确。原因如下：考虑数组[20, 100, 10, 12, 5, 13]。

[10, 12, 13]由于满足条件，因此结果对于该输入应该为真。

该算法确实对该测试返回 true，但如果我们在成功时记录a、b和的值，它们是，这不是正确的解决方案，因为这三个数字在原始数组中是无序的。c{ a: 5, b: 12, c: 13 }

可能发生以下两种情况之一：

  • 该算法是错误的。
  • 该算法仅仅验证所需子集的存在，但并未真正找到它。

我怀疑是后者，因为我无法构建一个算法给出错误结果的测试用例。但是，我无法理解为什么在像我所展示的那种情况下它保证是正确的。我还想知道返回正确子集的算法是否可以在 O(n) 时间和 O(1) 空间中工作。

arrays

2 个回答

  1. Best Answer

    您找到的解决方案代码是正确的。其背后的直觉是，如果b设置为输入数组中的某个值，那么您就知道之前有一个小于 的值，并且该值被分配给a。

    如果后来a得到了一个较小的值，这并不会改变当前值仍然是之前发生的较小值的证明的事实b- 我们只是不再存储它了a。

    如果在这种状态下我们发现一个大于 的值b，则证明存在一个递增三元组。我们可能不再引用该三元组中的第一个值，这并不重要。我们有该三元组中的第二个值这一事实足以作为证据。

    代码备注

    代码实际上不需要c变量，因为它始终是Infinity并且永远不会更新为其他任何变量。 finalelse不需要if链接到它。

    获得增加的三元组

    如果您想返回一个递增的三元组而不是仅仅true，那么当您找到 的较小值时a，不要将其存储在 中a，而是将其存储在临时的“缓冲区”（调用它newA或类似名称）中。只有在此之后您可以改进 的值，才能通过将其从“缓冲区”（）复制到 来b使 的值永久化。然后在最后的 中，您可以忽略 中可能存在的任何内容，因为它可能尚未通过 的后续新值变为“永久” ，因此将代表递增的三元组。anewAaelsenewAb[a, b, last value]

    不是必需的，但在 JavaScript 中，这种旧式for循环可以用循环重写，for..of因此您不需要使用索引i。

    看起来是这样的：

    var increasingTriplet = function (nums) {
    let newA = Infinity, a = Infinity, b = Infinity;

    for (const num of nums) {
        if (num <= newA) {
            newA = num; // Don't overwrite `a` yet...
        } else if (num <= b) {
            a = newA; // Now it is safe to overwrite `a`!
            b = num;
        } else {
            return [a, b, num];
        }        
    }
    return null;
}

const nums = [20, 100, 10, 12, 5, 13];
const triplet = increasingTriplet(nums);
console.log(triplet);

    • 2

  2. 注意： 的实际值b保证在此 'b' 之前满足较小的值。 的值a可能会被后面较小的值替换，但此操作不会改变正确子序列存在的事实older_a, b

    • 1

相关问题