🔗 🟡 2501. Longest Square Streak in an Array 1480

tags: Weekly Contest 323 陣列(Array) 二分搜尋(Binary Search) 排序(Sorting) 雜湊表(Hash Table) 動態規劃(Dynamic Programming)

題意

給定一個整數陣列 numsnums 。如果 numsnums 的子序列符合以下條件，則稱其為 平方連續子序列 ：

  • 子序列的長度至少為 22，且
  • 排序後 的子序列中，每個元素（除了第一個元素）都是前一個數字的 平方 。

返回 numsnums 中 最長平方連續子序列 的長度，或者如果沒有 平方連續子序列 ，則返回 −1-1。

子序列(Subsequence) 是可以通過從另一個陣列中刪除一些或不刪除任何元素，且不改變剩餘元素順序而派生出的陣列。

約束條件

  • 2≤nums.length≤1052 \leq nums.length \leq 10^5
  • 2≤nums[i]≤1052 \leq nums[i] \leq 10^5

思路

注意，雖然題目要求的是 子序列(Subsequence) ，但由於挑選出的子序列可以任意排序，因此事實上要求的是一個 子集合(Subset) 。

方法一：暴力檢查是否在集合中

由於我們要構成一個平方連續子序列，因此我們需要檢查每個元素的平方是否在集合中。

故我們可以先將所有元素放入集合 stst 中，接著遍歷每個元素 xx，持續檢查其平方是否也在集合 stst 中，

  • 如果 xx 的平方在集合 stst 中，則計數器 cntcnt 增加，並將 xx 更新為其平方值，繼續檢查下一個平方值。
  • 如果 xx 的平方不在集合 stst 中，則停止檢查，並更新答案。

最後，由於題目要求平方連續子序列的長度至少為 22，因此我們需要檢查答案是否大於等於 22，如果不大於等於 22，則返回 −1-1。

複雜度分析

  • 時間複雜度：O(nlog⁡log⁡M)O(n \log \log M)，其中 nn 是陣列長度，MM 是陣列中最大的數字。
    • 對於每個元素 xx，我們最多需要檢查 O(log⁡log⁡M)O(\log \log M) 次平方，因為數字會以平方的速度增長。
  • 空間複雜度：O(n)O(n)，其中 nn 是陣列長度。
    • 需要一個集合 stst 來儲存所有元素。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        st = set(nums)
        ans = 0
        for x in nums:
            cnt = 0
            while x in st:
                cnt += 1
                x *= x
            ans = max(ans, cnt)
        return ans if ans >= 2 else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        unordered_set<long long> st(nums.begin(), nums.end());
        int ans = 0;
        for (int x : nums) {
            long long tmp = x;
            int cnt = 0;
            while (st.find(tmp) != st.end()) {
                cnt++;
                tmp *= tmp;
            }
            ans = max(ans, cnt);
        }
        return ans >= 2 ? ans : -1;
    }
};

方法二：排序(Sorting) + 雜湊表(Hash Table) + 動態規劃(Dynamic Programming)

注意到在方法一中，我們可能會對一個數重複檢查多次，例如當 x=3x = 3 時，我們會重複檢查 32=9,92=81,812=65613^2=9, 9^2=81, 81^2=6561 等，但若這些數字皆在陣列中，我們就會重複檢查多次。

因此我們可以用 動態規劃(Dynamic Programming) 的思想，令 f(x)f(x) 表示以 xx 為開頭的最長平方連續子序列的長度，並將每個數字對應的最長平方連續子序列的長度記錄下來，這樣我們就可以避免重複檢查。

不過由於我們在檢查小數字時，會用到該數的平方，因此我們需要先對陣列由大到小進行排序。

在轉移時，我們需要檢查 xx 的平方 x2x^2 是否也在陣列中，如果不在，則 f(x)=1f(x) = 1；否則 f(x)=f(x2)+1f(x) = f(x^2) + 1。

同樣地，我們需要檢查答案是否大於等於 22，如果不大於等於 22，則返回 −1-1。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)，其中 nn 是陣列長度。
    • 需要對陣列進行排序。
  • 空間複雜度：O(n)\mathcal{O}(n)，其中 nn 是陣列長度。
    • 需要一個雜湊表 ff 來儲存每個數字對應的最長平方連續子序列的長度。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        f = defaultdict(int)
        ans = 1
        for x in nums:
            if x * x in f:
                f[x] = f[x * x] + 1
                ans = max(ans, f[x])
            else:
                f[x] = 1
        return ans if ans >= 2 else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        unordered_map<long long, int> f;
        int ans = 0;
        for (int x : nums) {
            if (f.count(1LL * x * x)) {
                f[x] = f[1LL * x * x] + 1;
            } else {
                f[x] = 1;
            }
            ans = max(ans, f[x]);
        }
        return ans >= 2 ? ans : -1;
    }
};

方法三：記憶化搜尋(Memoization)

注意到在方法二中，我們需要先對陣列進行排序，這樣會使得時間複雜度增加到 O(nlog⁡n)\mathcal{O}(n \log n)。這是因為 Bottom-up 的動態規劃需要從小到大遍歷每個數字，如果我們改為 Top-down 的動態規劃，則可以避免排序。

因此我們可以用 記憶化搜尋(Memoization) 的思想，同樣令 f(x)f(x) 表示以 xx 為開頭的最長平方連續子序列的長度，則我們在轉移時，只需要檢查 xx 的平方 x2x^2 是否也在集合 stst 中，如果不在，則 f(x)=0f(x) = 0；否則 f(x)=1+f(x2)f(x) = 1 + f(x^2)。由於是遞迴執行，因此此時 f(x2)f(x^2) 會先於 f(x)f(x) 被計算，我們不用使用排序。

但這種方法會有額外的遞迴呼叫開銷，因此雖然時間複雜度是最優的 O(n)\mathcal{O}(n)，但在本題的約束條件下，實際上會比其他方法慢。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)，其中 nn 是陣列長度。
    • 每個數字最多只會被計算一次，因為我們使用了記憶化技術來避免重複計算。
  • 空間複雜度：O(n)\mathcal{O}(n)，其中 nn 是陣列長度。
    • 使用了一個集合來存儲所有的數字，空間複雜度為 O(n)O(n)。
    • 對於每個數字只會保存一個記憶化值，因此空間複雜度為 O(n)O(n)。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        st = set(nums)
        @cache
        def dfs(x: int) -> int:
            if x not in st: return 0
            return 1 + dfs(x * x)
        ans = 0
        for x in st:
            ans = max(ans, dfs(x))
        return ans if ans >= 2 else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        unordered_set<long long> st(nums.begin(), nums.end());
        vector<int> memo(1e5 + 1, -1);
        auto dfs = [&](auto&& dfs, long long x) -> int {
            if (x > 1e5) return 0;
            int &res = memo[x];
            if (res != -1) return res;
            if (!st.count(x)) return res = 0;
            return res = 1 + dfs(dfs, x * x);
        };
        int ans = 0;
        for (int x : nums) {
            ans = max(ans, dfs(dfs, x));
        }
        return ans >= 2 ? ans : -1;
    }
};

寫在最後

PROMPT

Mystical Moonlight Encounter: A young anime girl, dressed in a black cape and witch hat, holds a pumpkin with an intense gaze. Standing before a large window framing a moonlit night sky, her focus is riveted on the pumpkin. To her left, a vibrant yellow pumpkin sits atop a straw bale amidst autumn leaves, adding a burst of warmth to the enchanting scene.