刷題日記(6)Majority Element

Rachel Yeh
Dec 29, 2020

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

— — — — —— — (第一種很聰明的解法QAQ) — — — — — — —

解題思路:摩爾投票法(成對移除)

  1. 取出list的第一個數放到一個暫存的變數(record)
  2. 然後將計數器counter設定為1 ,代表這個變數出現了一次
  3. 開始for迴圈,如果和(前面暫存的變數record)相等,則將計數器counter加1
  4. 如果和record不同且計數器>0時,將計數器 -1 (代表這兩個數成對移除了)
  5. 如果和record不同但是計數器=0時,將record更改為nums[i],並將計數器+1(代表前面的record已經成對移除完了,加入新的record)
  6. for迴圈跑完時,剩下的record就是答案(因為兩兩移除到最後剩下的一定是Major Element)
這段程式碼修改並來自https://ithelp.ithome.com.tw/articles/10213285,但不知為什麼leetcode的testcase過得了但正式run過不得了,不過應該是沒錯的
成對移除後只剩下最後一個2

「時間/空間複雜度?」
(O(n), O(1),除了一些變數以外我們沒有使用到額外的空間)

— — — —(第二種hash map的解法,多了空間複雜度) — — — —

解題思路:

  1. new一個新的HashMap
  2. 先拿出list的第一個數
  3. 設定max=0, 然後size變數等於list的長度除2
  4. 開始跑for loop,如果從list拿出來的數Hashmap沒有就放入key和value 1
  5. 如果key已經在Hashmap裡了,就給key把value拿出來之後再+1放回去
  6. 如果value大於max, max等於該value值, 然後記錄一下目前的major element, 然後其中當得到的value已經超過list size的一半,表示後面的數值其他再怎麼追也不會超過它,可以直接return 目前紀錄的Major Element
  7. 否則最後迴圈結束return Major Element

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet