題目資訊

• 題目編號: 2780
• 題目連結: Minimum Index of a Valid Split
• 主題: Array, Hash Table, Sorting

題目敘述

一個長度為 $m$ 的整數陣列 $arr$ 的元素 $x$ 是主導的，若陣列中超過一半的元素都是 $x$。

給你一個0索引的整數陣列 $nums$，長度為 $n$，其中有一個主導元素。

你可以在索引 $i$ 處將 $nums$ 分成兩個陣列 $nums[0, \ldots, i]$ 和 $nums[i + 1, \ldots, n - 1]$，但分割僅在以下條件下是有效的：

• $0 \leq i < n - 1$
• $nums[0, \ldots, i]$ 和 $nums[i + 1, \ldots, n - 1]$ 具有相同的主導元素。

這裡，$nums[i, \ldots, j]$ 代表從索引 $i$ 開始到索引 $j$ 結束的 $nums$ 子陣列，兩端皆包含。特別地，如果 $j < i$，則 $nums[i, \ldots, j]$ 代表空子陣列。

返回有效分割的最小索引。若不存在有效分割，返回 $-1$。

範例 1:

輸入: nums = [1,2,2,2]
輸出: 2
解釋: 我們可以在索引 2 處分割陣列以獲得陣列 [1,2,2] 和 [2]。
在陣列 [1,2,2] 中，元素 2 是主導的，因為它在陣列中出現兩次並且 $2 \times 2 > 3$。
在陣列 [2] 中，元素 2 是主導的，因為它在陣列中出現一次並且 $1 \times 2 > 1$。
[1,2,2] 和 [2] 具有和 nums 一樣的主導元素，所以這是有效分割。
可以證明索引 2 是有效分割的最小索引。

範例 2:

輸入: nums = [2,1,3,1,1,1,7,1,2,1]
輸出: 4
解釋: 我們可以在索引 4 處分割陣列以獲得陣列 [2,1,3,1,1] 和 [1,7,1,2,1]。
在陣列 [2,1,3,1,1] 中，元素 1 是主導的，因為它在陣列中出現三次並且 $3 \times 2 > 5$。
在陣列 [1,7,1,2,1] 中，元素 1 是主導的，因為它在陣列中出現三次並且 $3 \times 2 > 5$。
[2,1,3,1,1] 和 [1,7,1,2,1] 具有和 nums 一樣的主導元素，所以這是有效分割。
可以證明索引 4 是有效分割的最小索引。

範例 3:

輸入: nums = [3,3,3,3,7,2,2]
輸出: -1
解釋: 可以證明不存在有效分割。

約束條件:

• $1 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$
• $nums$ 恰好有一個主導元素。

直覺

這個問題要求識別出一個陣列中最小的索引，使得該陣列可以被拆分成兩個子陣列，且每個子陣列都有同一個主導元素。主導元素被定義為在各自子陣列中出現次數超過一半的元素。考慮到只有一個主導元素以及陣列的大小限制，我們可以運用一個二次遍歷的方法，以追蹤整體的主導元素及其在潛在分割中的出現次數來構造一個解。

解法

這個算法遵循以下主要步驟：

1. 識別主導元素：

   • 遍歷整個陣列，維護一個頻率映射來記錄每個元素的出現次數。
   • 同時跟蹤出現最頻繁的元素，即主導元素。

2. 確定最小有效分割索引：

   • 使用第二次遍歷陣列的方式，維護第一個子陣列中主導元素的出現次數，隨著算法的迭代進行更新。
   • 對於每個可能的分割索引 $i$，驗證：
     • 當前子陣列中主導元素的出現次數使得它在第一個子陣列中具主導地位，滿足 $dominantCount \times 2 > (i + 1)$。
     • 剩餘子陣列中主導元素的出現次數仍允許其保持主導地位，滿足 $(frequencyMap[dominantElement] - dominantCount) \times 2 > (n - i - 1)$，其中 $n$ 是陣列的長度。
   • 如果對於某個特定的索引，這兩個條件都滿足，則該索引為有效的分割點。

3. 返回結果：

   • 返回找到的第一個有效分割點的索引作為最小索引。
   • 如果在整個迭代過程中沒有發現有效的分割，那麼算法返回 $-1$。

這個方法通過利用頻率計算和關於主導性的條件，能夠高效地確定最小的分割索引。這保證了算法在 $O(n)$ 的複雜度下運行，符合問題的約束。

程式碼

C++

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        // 使用映射來儲存陣列中每個元素的頻率
        map<int, int> frequencyMap;

        // 用來追蹤最頻繁（支配）的元素的變數
        int dominantElement = nums.front();

        // 計算陣列中每個元素的頻率
        for (int num : nums) {
            if (++frequencyMap[num] > frequencyMap[dominantElement]) {
                dominantElement = num; // 如果目前的元素頻率更高，更新支配元素
            }
        }

        // 用來追蹤支配元素在第一部分分割中的頻率的變數
        int dominantCount = 0;

        // 遍歷陣列以尋找最小的有效分割索引
        for (int i = 0; i < nums.size() - 1; i++) {
            // 檢查當前元素是否是支配元素
            if (nums[i] == dominantElement) {
                dominantCount++;
            }

            // 檢查當前索引位置的分割是否有效
            if (
                dominantCount * 2 > i + 1 &&                                   // 在第一個子陣列中是支配的
                (frequencyMap[dominantElement] - dominantCount) * 2 > nums.size() - i - 1   // 在第二個子陣列中是支配的
               ) {
                return i; // 返回有效分割的最小索引
            }
        }

        return -1; // 如果沒有有效的分割，返回-1
    }
};

Python

class Solution:
    def minimumIndex(self, nums):
        # 用於儲存每個元素在陣列中頻率的映射
        frequencyMap = {}

        # 用於追蹤出現最頻繁（支配）的元素
        dominantElement = nums[0]

        # 計算陣列中每個元素的頻率
        for num in nums:
            frequencyMap[num] = frequencyMap.get(num, 0) + 1
            if frequencyMap[num] > frequencyMap.get(dominantElement, 0):
                dominantElement = num  # 如果當前元素的頻率較高，更新支配元素

        # 用於追蹤在分割的第一部分中支配元素的頻率
        dominantCount = 0

        # 遍歷陣列以找到最小的有效分割索引
        for i in range(len(nums) - 1):
            # 檢查當前元素是否為支配元素
            if nums[i] == dominantElement:
                dominantCount += 1

            # 檢查當前索引處的分割是否有效
            if (
                dominantCount * 2 > i + 1 and  # 在第一子陣列中是支配的
                (frequencyMap[dominantElement] - dominantCount) * 2 > len(nums) - i - 1  # 在第二子陣列中是支配的
            ):
                return i  # 返回有效分割的最小索引

        return -1  # 如果沒有有效分割，返回-1

複雜度分析

• 時間複雜度: $O(n)$

  該演算法的時間複雜度為 $O(n)$，其中 $n$ 是輸入陣列 nums 的長度。這是因為該演算法對陣列進行了兩次順序遍歷。第一次遍歷使用映射計算陣列中每個元素的頻率，這需要 $O(n)$ 的時間。第二次遍歷則是遍歷陣列以確定最小的有效分割索引，這同樣需要 $O(n)$ 的時間。由於這兩個操作是順序進行的，因此總的複雜度仍然是線性的。

• 空間複雜度: $O(n)$

  空間複雜度為 $O(n)$，這是由於使用了一個映射（frequencyMap）來儲存陣列中每個元素的頻率。在最壞的情況下，即所有元素都是唯一的情況下，映射需要為每個元素儲存一個頻率計數，因此空間需求與陣列的大小 $n$ 成正比。然而，除了映射之外，只使用了一個恆定數量的額外空間來儲存整數變數以追蹤主導元素和計數，因此整體空間複雜度是由映射驅動的。