Leetcode：(Python)(Array) Degree of an Array

題目連結：https://leetcode.com/problems/degree-of-an-array/description/

題目會給予一個 list，我們要找出出現頻率最高的數字，同時找出包含所有出現頻率最高數字的最小 Sub list.

• 出現頻率最高數字可能不只一個
• 最小 sub list長度只有一個數字

e.g.

總共有 1,2,3三個數字，1出現的頻率是2次，2出現的頻率是2次，3出現的頻率是1次。

1和2出現的頻率最高，1最小的 sub list是 [1,2,2,3,1]，2最小的 sub list是 [2,2]，因此答案是 2。

初始想法

• 找出出現頻率最高的數字
• 找出這些數字的最小 list

光想就是要用迴圈反覆針對每個數字找，先來偷看別人答案

參考他人作法

他人作法連結：https://leetcode.com/problems/degree-of-an-array/solutions/2899095/python-simple-explanation-one-pass-beats-99/?orderBy=hot&languageTags=python

用迴圈逐一掃過每一個數字

如果數字尚未出現過

• 數字出現的頻率 + 1
• 數字最右方的位置 = 數字最右方的位置 = 第一次出現的位置

數字已經出現過

• 數字出現的頻率 + 1
• 數字最右方的位置 +1

接著找出頻率的最大值，逐一確認頻率最大值的最左和最右邊位置差異（即 sub list長度）

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        number = {}
        left = {}
        right = {}

        for p, n in enumerate(nums):
            if n in number:
                number[n] += 1
                right[n] = p
            else:
                number[n] = 1
                left[n] = p
                right[n] = p

        print('number:',number)
        print('left:',left)
        print('right:',right)

        max_freq = max(number.values())
        min_length = len(nums)
        for n in number:
            if number[n] == max_freq:
                min_length = min(right[n]-left[n]+1, min_length)

        return min_length

為了避免多次迴圈，在迴圈逐一確認數字時也把頻率和位置都記錄，最後用 dictionary來查找就會很快。

2024-09-09

這一題要找出的條件比較複雜

1. 出現頻率最高的數字
2. 包含出現頻率最高數字的最小數組 -> 要記錄數字的頭尾

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        #紀錄數字出現的第一個位置，最後一個位置，頻率
        first_position, last_position, frequency = {}, {}, {}

        for i, n in enumerate(nums):
            #數字第一次出現才寫入 first_position
            if n not in first_position:
                first_position[n] = i

            #數字每一次出現都寫入 last_position，迭代更新
            last_position[n] = i
            frequency[n] = frequency.get(n, 0) + 1

        degree = max(frequency.values())
        #預設為最大長度，迭代減少
        min_len = len(nums)
         
        #出現頻率最高的數字可能有多個，要逐個檢查長度
        for f in frequency:
            if frequency[f] == degree:
                min_len = min(last_position[f] - first_position[f] + 1, min_len)

        return min_len