題目資訊

題目編號: 1007
題目連結: Minimum Domino Rotations For Equal Row
主題: Array, Greedy

題目敘述

在一列多米諾骨牌中，tops[i] 和 bottoms[i] 代表第 $i$ 個多米諾骨牌的上半部分和下半部分。（多米諾骨牌是一個具有兩個數字的瓷磚，數字範圍為 1 到 6——每半邊一個數字。）

我們可以旋轉第 $i$ 個多米諾骨牌，使 tops[i] 和 bottoms[i] 互換數值。

返回最小旋轉次數，使得 tops 中的所有數值相同，或者 bottoms 中的所有數值相同。

如果無法達成，返回 -1。

範例 1：

dominoes

輸入: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
輸出: 2
解釋： 
第一幅圖代表按給定的 `tops` 和 `bottoms` 擺放的多米諾骨牌：在我們進行任何旋轉之前。
若我們旋轉第二個和第四個多米諾骨牌，可以使頂部每個數值都等於 2，如第二幅圖所示。

範例 2：

輸入: tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
輸出: -1
解釋： 
在這個情況下，不可能通過旋轉多米諾骨牌，使其中一行的值都相等。

約束條件：

$2 \leq \text{tops.length} \leq 2 \times 10^4$
$\text{bottoms.length} == \text{tops.length}$
$1 \leq \text{tops}[i], \text{bottoms}[i] \leq 6$

直覺

這個問題可以被視作將所有的多米諾骨牌排列成一行，以達到其頂部或底部所有的數字相同。我們允許單獨旋轉每個多米諾骨牌，將其頂部和底部的數字對調。主要的挑戰在於確定所需旋轉的最小次數，或者確認根本不可能達成全部數字在一行中相同。然而，由於每個數字的範圍限制在1到6之間，我們可以利用這一點，通過計算每個數字出現的次數來高效地找到解決方案。

解法

這個演算法包含多個關鍵步驟來確定最小旋轉次數：

計數出現次數：初始化三個向量，以追踪每個數字（從1到6）的出現頻率，分別出現在多米諾骨牌的頂部（topCount）、底部（bottomCount）和總體（totalCount）中。
填充頻率計數器：遍歷每個多米諾骨牌的位置，更新頻率計數器：
- 若當前多米諾骨牌的頂部出現某數字，則增加 topCount 對應的計數。
- 若底部出現某數字，則增加 bottomCount 對應的計數。
- 若頂部出現某數字，則增加 totalCount 對應的計數。若頂部和底部的數字不同，則也增加 totalCount 對應底部數字的計數。
檢查可行性：確定是否能使整行的數字相同。如果沒有任何數字在頂部和底部的出現次數總和達到 len，則不可能使整行數字相同，因此返回 -1。
計算最小旋轉次數：對於有潛力填滿整行的數字（即其總出現次數等於多米諾骨牌陣列長度 len），計算所需的最小旋轉次數：
- 對於每個可能的數字，所需的最小旋轉次數為多米諾骨牌數量減去該數字在頂部或底部出現的最大次數。
- 相應地更新最小旋轉次數。
返回結果：若存在可行的數字，則最小旋轉次數將有意義並作為結果返回。否則，該值將保留為 INT_MAX 並需要進行調整。

通過將問題分解成計數和可行性檢查步驟，這種方法有效地確定多米諾骨牌是否以及如何能通過最少的旋轉來重新排列完成目標。該方法既能有效率地處理時間，又非常符合問題的限制。

程式碼

C++

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        int len = tops.size();
        int minRotations = INT_MAX;

        // 向量來計算每個數字(1到6)在頂部和底部出現的次數。
        vector<int> totalCount(6, 0), topCount(6, 0), bottomCount(6, 0);

        // 計算每個數字在tops和bottoms中出現的次數。
        for (int i = 0; i < len; i++) {
            topCount[tops[i] - 1]++;
            bottomCount[bottoms[i] - 1]++;
            totalCount[tops[i] - 1]++;
            if (tops[i] != bottoms[i]) {
                totalCount[bottoms[i] - 1]++;
            }
        }

        // 如果沒有數字可以填滿整行，返回-1。
        if (*max_element(totalCount.begin(), totalCount.end()) < len) {
            return -1;
        }

        // 計算使整行數值相同所需的最少旋轉次數。
        for (int i = 0; i < 6; i++) {
            if (totalCount[i] == len) {
                minRotations = min(minRotations, len - max(topCount[i], bottomCount[i]));
            }
        }

        return minRotations;
    }
};

Python

class Solution:
    def minDominoRotations(self, tops, bottoms):
        from sys import maxsize

        len_tops = len(tops)
        min_rotations = maxsize

        # 用於計算每個數字（1 到 6）在上層和下層中出現的次數的列表。
        total_count = [0] * 6
        top_count = [0] * 6
        bottom_count = [0] * 6

        # 計算每個數字在 tops 和 bottoms 中出現的次數。
        for i in range(len_tops):
            top_count[tops[i] - 1] += 1
            bottom_count[bottoms[i] - 1] += 1
            total_count[tops[i] - 1] += 1
            if tops[i] != bottoms[i]:
                total_count[bottoms[i] - 1] += 1

        # 如果沒有數字可以填滿整個行，返回 -1。
        if max(total_count) < len_tops:
            return -1

        # 計算需要旋轉的最少次數以使一行中的所有值相同。
        for i in range(6):
            if total_count[i] == len_tops:
                min_rotations = min(min_rotations, len_tops - max(top_count[i], bottom_count[i]))

        return min_rotations

複雜度分析

時間複雜度: 演算法多次遍歷數組。第一個迴圈的時間複雜度為 $O(n)$，用於計算 tops 和 bottoms 數組中每個數字的出現次數，其中 $n$ 是 tops（或 bottoms）數組的長度。接下來是 max_element 的常數時間操作，由於 totalCount 的大小始終為 6，因此需要 $O(1)$。最後一個迴圈遍歷固定大小的數組（1 到 6 範圍的 6 個元素），因此也是 $O(1)$。因此，總的時間複雜度為 $O(n)$。
空間複雜度: 空間複雜度為 $O(1)$，因為演算法使用的額外空間不隨輸入大小 n 而變化。我們使用固定數量的額外空間，即三個數組（totalCount，topCount，bottomCount），每個有 6 個元素來存儲計數，以及一些整數變量。因此，無論 n 為何，空間使用量都保持不變。

CS Note
En

Leetcode 1007. Minimum Domino Rotations For Equal Row

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析