Typescript 編碼編年史：增加三元組子序列-js教程-PHP中文網

Typescript 編碼編年史：增加三元組子序列

WBOY

發布： 2024-07-17 21:13:42

原創

1122 人瀏覽過

Typescript Coding Chronicles: Increasing Triplet Subsequence

問題陳述：

給定一個整數數組nums，如果存在索引三元組(i, j, k) 且i

範例1：

輸入：nums = [1,2,3,4,5]
輸出：true
解釋：任何 i

範例2：

輸入：nums = [5,4,3,2,1]
輸出：假
解釋：不存在三元組。

範例3：

輸入：nums = [2,1,5,0,4,6]
輸出：true
解釋：三元組 (3, 4, 5) 有效，因為 nums[3] == 0

限制條件：

1
-2^31

後續：

你能實作以 O(n) 時間複雜度和 O(1) 空間複雜度運作的解決方案嗎？

初步思考過程：

為了有效地解決這個問題，我們需要追蹤迄今為止遇到的最小和第二小的值。如果我們找到大於第二小的值的第三個值，那麼我們就找到了遞增三元組。

基本解決方案（暴力）：

暴力解決方案涉及檢查所有可能的三元組，看看是否存在滿足條件 i

代碼：

function increasingTripletBruteForce(nums: number[]): boolean {
    const n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] < nums[j] && nums[j] < nums[k]) {
                    return true;
                }
            }
        }
    }
    return false;
}

登入後複製

時間複雜度分析：

時間複雜度： O(n^3)，其中 n 是陣列的長度。這是因為我們正在檢查所有可能的三元組。
空間複雜度： O(1)，因為我們沒有使用任何額外的空間。

限制：

暴力解決方案效率不高，不適合大輸入。

優化方案：

最佳化的解決方案涉及迭代數組，同時維護兩個變量，第一和第二，它們代表迄今為止遇到的最小和第二小的值。如果我們找到大於秒的值，則傳回 true。

代碼：

function increasingTriplet(nums: number[]): boolean {
    let first = Infinity;
    let second = Infinity;

    for (let num of nums) {
        if (num <= first) {
            first = num; // smallest value
        } else if (num <= second) {
            second = num; // second smallest value
        } else {
            return true; // found a value greater than second smallest, thus an increasing triplet exists
        }
    }

    return false;
}

登入後複製

時間複雜度分析：

時間複雜度： O(n)，其中 n 是陣列的長度。我們迭代數組一次。
空間複雜度： O(1)，因為我們只使用恆定量的額外空間。

基本解決方案的改進：

此解決方案以線性時間運行並使用恆定空間，使其對於給定的約束是最佳的。

邊緣情況和測試：

邊緣情況：

數組依降序排列。
此數組恰好包含三個按升序排列的元素。
數組有大量元素且沒有遞增的三元組。
陣列包含重複項。

測試用例：

console.log(increasingTripletBruteForce([1,2,3,4,5])); // true
console.log(increasingTripletBruteForce([5,4,3,2,1])); // false
console.log(increasingTripletBruteForce([2,1,5,0,4,6])); // true
console.log(increasingTripletBruteForce([1,1,1,1,1])); // false
console.log(increasingTripletBruteForce([1,2])); // false
console.log(increasingTripletBruteForce([1,2,3])); // true
console.log(increasingTripletBruteForce([1,5,0,4,1,3])); // true

console.log(increasingTriplet([1,2,3,4,5])); // true
console.log(increasingTriplet([5,4,3,2,1])); // false
console.log(increasingTriplet([2,1,5,0,4,6])); // true
console.log(increasingTriplet([1,1,1,1,1])); // false
console.log(increasingTriplet([1,2])); // false
console.log(increasingTriplet([1,2,3])); // true
console.log(increasingTriplet([1,5,0,4,1,3])); // true

登入後複製