DEV Community

vc7
vc7

Posted on • Edited on

1

LeetCode in Swift - 1975. Maximum Matrix Sum (中文解釋)

題目

2024/11/24 的每日一題


資料結構與演算法

  • 矩陣
  • 貪婪
  • 數學

題意

可以挑任意兩個數字都乘以 -1 ,已達到整個矩陣所有元素的和為最大值

意味著

  1. 負數能變正數,正數能為負數
  2. Greedy - 可以先加總所有元素值的絕對值作為總和
    • 當負數為 偶數 個時,透過無限次數的 -1 轉換,能夠都轉為正數,這時候就可以直接回傳
    • 當負數為 奇數 個時,一定會有一個負數會落單,這時候我們會希望落單的負數是最大,換言之是絕對值最 的負數。因為當絕對值越大,越能貢獻總和成為更大的數。
      • 接著回傳的總和必須扣掉這個數兩次,一次是 扣掉絕對值 ,一次是 加上負數值
  3. 挑負數值
    • 當負數值只剩下一個的時後,必須要考慮像是這樣的 case ,當最小正數比負數的絕對值還要小
      • 最小正數 1, 負數 -3
      • 因為負數變成絕對值後能貢獻的值比較大,這時候就可以呼應 1. 把最小正數轉換乘負數 -1 ,令其成為「落單的負數」。

Routine

解析完題意後,就可以來制定 routine 該做什麼事。這題的 routine 就只有一件事情: 走訪矩陣的每個元素

走訪矩陣

走訪矩陣需要先準備這幾個變數:

  • 總和
  • 最小絕對值
  • 負數的個數

走訪過程

  1. 把元素的絕對值加到 總和
  2. 為了「落單的負數」比較和更新 最小絕對值
  3. 當前元素為負值時,進行 負數的個數 += 1

後處理

  1. 當負數個數為 偶數 → 回傳 總和 不做其他運算
  2. 當負數個數為 奇數 → 把多加了的 最小絕對值總和 扣掉一次後,再加上負值的 最小絕對值

程式碼

class Solution {
    func maxMatrixSum(_ matrix: [[Int]]) -> Int {
        var sum = 0
        var minimum = Int.max
        var negativeCount = 0

        for row in matrix {
            for column in row {
                sum += abs(column)
                minimum = min(minimum, abs(column))

                if column < 0 {
                    negativeCount += 1
                }
            }
        }

        guard negativeCount % 2 != 0 else {
            return sum
        }

        // sum - absolute min + the negative min
        return sum - minimum - minimum
    }
}
Enter fullscreen mode Exit fullscreen mode

複雜度分析

依題目,陣列大小為 n x n

  • 時間複雜度: O(nxn) 或 O(n^2)
    • 線性走訪矩陣,元素個數為 n x n
  • 空間複雜度: O(1)
    • 雖然宣告了三個變數為 O(3) ,但是表示時可寫成 O(1)

結語

以上,如果有什麼回饋,歡迎在留言區跟我說,謝謝!

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay