🔗 🟡 1286. Iterator for Combination

tags: Biweekly Contest 15

題意

請你設計一個 Iterator 類別 CombinationIterator，包含以下內容：

  • CombinationIterator(string characters, int combinationLength) 一個 Constructor，輸入參數包括：用一個 有序 且字元 不重複 的字符串 characters（該字符串只包含小寫英文字母）和一個數字 combinationLength（以下用 kk 表示）。
  • next() 按 字典序 返回長度為 kk 的下一個字母組合。
  • hasNext() 只有存在長度為 combinationLength 的下一個字母組合時，才返回 true，否則返回 false。

約束條件

  • 1≤k≤characters.length≤151 \leq k \leq \text{characters.length} \leq 15
  • characters 的所有字母都是 不同 的。
  • 最多會進行 10410^4 次 next 和 hasNext 的調用。
  • 保證每次調用函數 next 時都存在下一個字母組合。

思路

本題和 31. Next Permutation [🔗解題紀錄] 類似，分別是求解下一個排列和下一個組合。但求解組合其實比求解排列要簡單，因為組合的元素是無序的，因此不用考慮誰先誰後，只需要考慮有哪些元素在組合中。

類似地，由於要找到在所有比當前組合大的組合中，字典序最小的組合，我們應盡可能少修改 nums 前方的元素。換句話說，如果我們可以透過 修改 最後的 lnln 個元素，得到更大的排列，那麼在 lnln 最小的情況，我們可以得到恰好緊跟在 nums 之後的排列。注意這裡和排列的情況不同，排列的情況由於要使用所有元素，因此只能交換，但這裡能直接修改。

為了知道組合中的元素是集合中的第幾個元素，我們使用一個陣列 combscombs 來記錄每個元素的下標，若 combs[i]=jcombs[i] = j，則表示組合中的第 ii 個元素是集合中第 jj 大的元素。

如此便可以確定核心思路，從 ln=1ln=1 開始，依次檢查是否能改變最後 lnln 個元素得到更大的排列。

  • 不難發現若無法修改，則最後 lnln 個元素一定是最大的 lnln 個元素。換句話說，當存在某個下標 ii 可以得到更大的組合時，combs[k−1]=n−1,combs[k−2]=n−2,...,combs[i+1]=n−k+(i+1)combs[k-1] = n - 1, combs[k-2] = n - 2, ..., combs[i+1] = n - k + (i + 1) 且 combs[i+1]−combs[i]>1combs[i+1] - combs[i] > 1。
  • 因此，我們由後往前移動指標 ii，直到找到可以第一個修改的元素位置，即 combs[i]≠n−k+icombs[i] \neq n - k + i 的位置。

接著考慮如何修改 combscombs 的值，使得組合變大。

  • 首先將 combs[i]=combs[i]+1combs[i] = combs[i] + 1，這樣就保證能得到比當前組合大的組合。
  • 之後要使後續的元素盡可能的小，但由於組合是無序的，因此只能添加比 combs[i]combs[i] 大的元素。在這其中最小的顯然是 combs[i]+1combs[i] + 1。因此可以將 combs[i+1]combs[i+1] 到 combs[k−1]combs[k-1] 的值設定為 combs[i]+1,combs[i]+2,...,combs[i]+(k−i−1)combs[i] + 1, combs[i] + 2, ..., combs[i] + (k - i - 1)，實作時只需要設定成 combs[j]=combs[j−1]+1combs[j] = combs[j-1] + 1 即可。

最後，考慮如何確定沒有下一個組合。當遍歷完所有元素，仍無法找到可以修改的元素，則表示當前已經是最大的組合，故不存在下一個組合。

複雜度分析

  • 時間複雜度：
    • next 的時間複雜度：O(k)\mathcal{O}(k)，每次調用 next 時，最多需要遍歷 O(k)O(k) 個元素。
      • 這裡雖然看似是兩重迴圈，但實際上第二個迴圈只有在找到可以修改的元素時才會執行。
    • hasNext 的時間複雜度：O(1)\mathcal{O}(1)，只需要檢查 has_next 的值。
  • 空間複雜度：O(n+k)\mathcal{O}(n + k)，需要使用 O(n)O(n) 個額外空間來保存字串，以及 O(k)O(k) 的額外空間來儲存組合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.n = len(characters)
        self.k = combinationLength
        self.s = list(characters)
        self.comb = list(range(self.k))
        self.has_next = True

    def next(self) -> str:
        ans = "".join([self.s[p] for p in self.comb])
        for i in range(self.k - 1, -1, -1):
            if self.comb[i] != self.n - self.k + i:
                self.comb[i] += 1
                for j in range(i + 1, self.k):
                    self.comb[j] = self.comb[j - 1] + 1
                break
        else:
            self.has_next = False
        return ans

    def hasNext(self) -> bool:
        return self.has_next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class CombinationIterator {
public:
    int n, k;
    vector<int> comb;
    bool has_next;
    string s;

    CombinationIterator(string characters, int combinationLength) {
        n = characters.size();
        k = combinationLength;
        s = characters;
        comb = vector<int>(k);
        iota(comb.begin(), comb.end(), 0);
        has_next = true;
    }
    
    string next() {
        string ans = "";
        for (int i = 0; i < k; ++i) {
            ans += s[comb[i]];
        }
        bool flag = false;
        for (int i = k - 1; i >= 0 && !flag; --i) {
            if (comb[i] != n - k + i) {
                comb[i]++;
                for (int j = i + 1; j < k; ++j) {
                    comb[j] = comb[j - 1] + 1;
                }
                flag = true;
            }
        }
        if (!flag) {
            has_next = false;
        }
        return ans;
    }
    
    bool hasNext() {
        return has_next;
    }
};

類題

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

1other, solo, no humans, Sylveon, Sylveon (Pokémon), Pokémon, blue eyes, full body, outdoors, sky, day, o, blue sky, grass, grassland, looking up,

A serene hand-drawn scene featuring Sylveon, a Pokémon with flowing ribbons, standing in a vibrant green meadow under a clear blue sky. Its eyes are blue, and its ears are a vibrant shade of pink, while its tail is a lighter shade of gray. The ribbons are gently swaying in the wind, and the art style is soft and painterly, emphasizing tranquility and freedom. Detailed grass in the foreground contrasts with the bright, open sky.

同樣是來自群組，106中央的數學題目。