破題

這個演算法的目的是將一幅畫作分割成多個區段，每個區段都有自己的顏色。畫作由多個區段組成，每個區段都有一個起始點、結束點和顏色。如果兩個區段重疊，那麼重疊部分的顏色將是兩個區段顏色的總和。

別閉門造車，一起準備面試吧！
在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！
我們將幫助您撰寫一份出色的履歷表，讓您在眾多求職者中脫穎而出。我們將為您提供專業的建議和指導，幫助您在履歷上呈現最完美的自己。如果心動的話，就別猶豫啦！趕快把握機會，動動手指投遞履歷吧！立即加入 Line 讀書會，和大家一起實現夢想！

履歷諮詢	加入讀書會 (邀請碼：6428)

解題思路

1. 我們找出所有區段中最大的 index，並宣告一個長度為最大 index+1 的陣列，陣列中每個元素都是一個 Set，用來存儲該 index 位置的顏色。
2. 我們遍歷所有區段，將每個區段的起始點和結束點對應的 Set 中加上該區段的顏色。如果是結束點，則加上負數顏色。
3. 我們遍歷宣告的陣列，計算每個 index 位置的顏色總和。如果當前 index 位置的顏色總和與前一個 index 位置的顏色總和不同，或者當前 index 位置的 Set 與前一個 index 位置的 Set 不同，那麼我們就找到了一個新的區段，要將它加到答案中。

程式

class Solution {
    fun splitPainting(segments: Array<IntArray>): List<List<Long>> {
        var maxIndex = 0
        segments.forEach { segment ->
            if (segment[0] > maxIndex) maxIndex = segment[0]
            if (segment[1] > maxIndex) maxIndex = segment[1]
        }
        val longArray = Array<Set<Long>>(maxIndex + 1) { mutableSetOf() }
        segments.forEach { segment ->
            val color = segment[2].toLong()
            longArray[segment[0]] = longArray[segment[0]].toMutableSet().apply {
                add(color)
            }
            longArray[segment[1]] = longArray[segment[1]].toMutableSet().apply {
                add(-color)
            }
        }
        val ans = mutableListOf<List<Long>>()
        var color = 0L
        var left = longArray.indexOfFirst { it.sum() != 0L }
        var prevSet = longArray[left]
        longArray.forEachIndexed { index, set ->
            val nextColor = if (index > 0) set.sum() + color else set.sum()
            if (color != nextColor) {
                if (index.toLong() > left && color!= 0L) {
                    ans.add(listOf(left.toLong(), index.toLong(), color))
                }
                left = index
            } else if (set != prevSet && set != setOf<Long>() && color!= 0L) {
                ans.add(listOf(left.toLong(), index.toLong(), color))
                left = index
            }
            color = nextColor
        }

        return ans
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是 segments 的長度。我們需要遍歷所有 segments 來宣告陣列，然後再遍歷陣列以找到所有新的區段。

• 空間複雜度:
  ，其中 是 segments 中最大的 index。我們需要宣告一個長度為最大 index+1 的陣列來存儲每個 index 位置的顏色。在最壞情況下，這可能需要與 segments 中最大 index 相同大小的空間。

　更多 LeetCode 解答在此，一起來學習！

別閉門造車，一起準備面試吧！

在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！

履歷諮詢	加入讀書會 (邀請碼：6428)