LeetCode 解題：Find Pivot Index

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/find-pivot-index/

中文描述

給定一個整數陣列 nums ，找出某目標索引位置 Pivot Index，讓目標索引位置的左邊元素陣列元素總和等於目標索引位置的右邊陣列元素總和，總和不包含目標索引位置之值。

範例一：

輸入 nums = [1, 2, 3, 4, 2, 2, 2] 

輸出  3

因為  [1, 2, 3] 總和等於 6 等於 [2, 2, 2]總和

範例二：

輸入 nums = [3, -3, 3] 

輸出  0

因為  [] 總和等於 0 等於 [-3, 3] 總和

解法一：

暴力法。對每一個索引位置算出左邊元素陣列元素總和 leftSum 與右邊元素陣列元素總和 rightSum 是否相等。

Python Code

class Solution:

    def pivotIndex(self, nums: List[int]) -> int:

        total = sum(nums) # 陣列總和

        leftSum = 0 # 左邊總和

        for i in range(len(nums)): # 從左邊索引0開始找起

            rightSum = sum(nums[i+1:]) # 右邊總和

            leftSum = total - rightSum - nums[i] # 左邊總和

            if leftSum == rightSum: # 若一樣

                return i # 找到 Pivot Index

        return -1

解法二：

算出右邊總和 rightSum，與 leftSum 等於零。從索引位置0開始依序從 rightSum 刪除 nums[i] 數值，判斷 leftSum 是否等於 rightSum，若有，則找到。leftSum 開始依序加入 nums[i] 數值。

Python Code

class Solution:

    def pivotIndex(self, nums: List[int]) -> int:

        rightSum = sum(nums) # 右邊總和

        leftSum = 0 # 左邊總和

        for i in range(len(nums)): # 從左邊索引0開始找起

            rightSum -= nums[i]

            if leftSum == rightSum: # 若一樣

                return i # 找到 Pivot Index

           

            leftSum += nums[i]

        return -1

LeetCode 解題練習：Find All Numbers Disappeared in an Array

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

中文描述

給定一個含有[1, n] 之間的n個元素之整數陣列 nums (陣列長度為 n)，找出[1, n] 之間沒有出現在 陣列 nums 元素中的整數。 

範例一：

輸入 nums = [2, 2] 

輸出 [1]

範例二：

輸入 nums = [1, 2, 2] 

輸出 [3]

範例三：

輸入 nums = [1, 2, 1, 2, 1, 3, 4] 

輸出 [5, 6, 7]

解法一：

使用計數的方式記錄[1,n]每一個數字出現在 nums 的次數，再統計出現次數為0的數字有哪些。

Python Code

class Solution:

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:

        n = len(nums)

        counts = [0] * n # 計算 [1,n] 數字出現的次數

       

        for i in nums:

            counts[i - 1] += 1 # 出現一次就增加1

       

        missingNumbers = [] # 沒出現在 nums 的數字

       

        for i in range(n):

            if counts[i] == 0: # 若出現次數為0次

                missingNumbers.append(i+1) # 加入到未出現之數字清單

       

        return missingNumbers

解法二：

使用不包含重複資料的資料結構，例如集合 set、字典 dictionary 來存放 nums 陣列中的數字，再找出沒有出現的數字。 

Python Code

class Solution:

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:

        uniquedNumbers = set(nums) # 去除重複的數字

        disappearedNumbers = [] # 存放 [1, n] 中沒有在 nums 出現的數字

        for n in range(1, len(nums) + 1): # 走訪 [1,n] 數字

            if n not in uniquedNumbers: # 若沒有出現在 nums 中

                disappearedNumbers.append(n) # 加入沒有出現的數字清單中

       

        return disappearedNumbers

解法三：

讓有出現在 nums 的數字 i ，當成索引後，變更 nums[i] 為有負號，在統計 nums[i] 中有哪些 nums[i] 值為大於零，i 值為未出現在 nums 的數字。

Python Code

class Solution:

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:

       

        for i in nums:

            idx = abs(i) - 1 # 索引為 i 之正值減去 1

            if nums[idx] > 0: # 若大於零

                nums[idx] = -nums[idx] # 變成負數， i 標記為有出現

       

        missingNumbers = [] # 沒出現在 nums 的數字

       

        for i in range(len(nums)):

            if nums[i] > 0: # 若大於零，代表 i 未出現在 nums 中

                missingNumbers.append(i+1) # 加入到未出現之數字清單

       

        return missingNumbers

LeetCode 解題練習：Height Checker

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/height-checker/ 

中文描述

給定一個整數陣列 heights ，請算出 heights 中沒有依照由小到大之順序的元素個數。

範例一：

輸入 heights = [3, 1, 2] 

輸出 3

因為依照小到大的陣列為 [1, 2, 3] ，heights 每個元素皆不再所屬的排序位置上。

範例二：

輸入 heights = [1, 3, 2] 

輸出 2

因為依照小到大的陣列為 [1, 2, 3] ，heights[0]有在排序的位置上，其餘元素皆不在所屬的排序位置上。

範例三：

輸入 heights = [1, 2, 3] 

輸出 0

因為依照小到大的陣列為 [1, 2, 3] ，heights所有元素皆在所屬的排序位置上。

解法：

先用內建排序函式產生由小排到大的 expected 陣列，依照索引位置 i 算出 heights[i] != expected[i] 有多少個。

Python Code

class Solution:

    def heightChecker(self, heights: List[int]) -> int:

        expected = sorted(heights)

        notMatch = 0

        for i in range(len(heights)):

            if heights[i] != expected[i]:

                notMatch += 1

        return notMatch