陣列操作入門題 Sort Array By Parity Leetcode #905

閱讀時間約 2 分鐘
raw-image

這題的題目在這裡

題目會給定一個陣列,要求我們把裡面的數字依照奇偶數去排序
偶數的排在前面,奇數的排在後面


測試範例:

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
偶數排在前面,奇數排在後面。​

Example 2:

Input: nums = [0]
Output: [0]

約束條件:

Constraints:

  • 1 <= nums.length <= 5000
  • 0 <= nums[i] <= 5000

演算法:

雖然題目名字提到了排序sort,但是我們不需要真的去使用O(n log n)的排序演算法。

為什麼?

因為題目要求的條件其實比較寬鬆,並沒有要求比大小,只需要奇偶數區分開來即可。

那麼我們可以使用雙指針的技巧,一個指針負責掃描所有元素,另一個指針負責把偶數swap到相對前面的位置(相較之下,在swap之後,奇數自然就落在後面的位置)。


程式碼:

class Solution:
 def sortArrayByParity(self, A: List[int]) -> List[int]:
  
  idx_of_even = 0
  
  is_even_number = lambda x: not( x & 1 )
  
  for i in range(len(A)):
   # scan each element
   
   if is_even_number(A[i]):
   
    # swap even number to the left-hand side
    
    A[idx_of_even], A[i] = A[i], A[idx_of_even]
    idx_of_even += 1
    
  return A

時間複雜度:

O( n ) 每個元素掃描一遍即可。

空間複雜度:

O( 1 ) 只使用到固定一組雙指針,所占用的記憶體空間固定為常數級別O( 1 )


其實這題的swap概念,和quick sort 內部在做分割 partition的那個模組很像,讀者空閒之餘可以細細體會,其實觀念是相通的。

raw-image

Reference:

[1] Python O(n) by two-pointers [w/ Visualization] - Sort Array By Parity - LeetCode

85會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目會給定一個2D 二維的矩陣,矩陣內的元素值代表對應的高度,要求我們找出相對最高點,也就是(大樓)高度大於N4 東、南、西、北 四個鄰居的索引值。 題目保證矩陣內相鄰的元素值都不相同,也又是相鄰的兩兩相比較,一定有一個比較高,有一個比較矮。
題目會給定一個陣列,陣列裡面的元素分布就像一座山峰。 最大值的左邊都是上坡段,最大值的右邊都是下坡段。 要求我們找出陣列裡面的絕對極大值(absolute max value)所在的陣列索引
題目會給定一個陣列,裡面有大有小,可以把數字的大小類比成高度 要求我們找出陣列裡面的相對極大值(relative max value)所在的陣列索引 也就是說當下這個元素,大於左邊鄰居的元素值,也大於右邊鄰居的元素值
題目會給定我們一個陣列,並且定義了一種三角形合併的操作。 當下這一排相鄰的兩項相加,對mod 10取餘數,會成為下一排的對應項,一直反覆操作,直到剩下一個元素為止。 要求我們返回最後一層的答案。 測試範例: Example 1: Input: nums = [1,2,
這題的題目在這裡 題目會給定一個輸入整數x, 要求我們返回x的正整數平方根(取無條件捨去小數部分的正整數值)
這題基本上是前一題巴斯卡三角形的孿生題,那題和這題的本質是完全一樣的,只是題目要求稍有不同。 前一題求的是整個巴斯卡三角形,這一題求的是巴斯卡三角形的最後一層。
題目會給定一個2D 二維的矩陣,矩陣內的元素值代表對應的高度,要求我們找出相對最高點,也就是(大樓)高度大於N4 東、南、西、北 四個鄰居的索引值。 題目保證矩陣內相鄰的元素值都不相同,也又是相鄰的兩兩相比較,一定有一個比較高,有一個比較矮。
題目會給定一個陣列,陣列裡面的元素分布就像一座山峰。 最大值的左邊都是上坡段,最大值的右邊都是下坡段。 要求我們找出陣列裡面的絕對極大值(absolute max value)所在的陣列索引
題目會給定一個陣列,裡面有大有小,可以把數字的大小類比成高度 要求我們找出陣列裡面的相對極大值(relative max value)所在的陣列索引 也就是說當下這個元素,大於左邊鄰居的元素值,也大於右邊鄰居的元素值
題目會給定我們一個陣列,並且定義了一種三角形合併的操作。 當下這一排相鄰的兩項相加,對mod 10取餘數,會成為下一排的對應項,一直反覆操作,直到剩下一個元素為止。 要求我們返回最後一層的答案。 測試範例: Example 1: Input: nums = [1,2,
這題的題目在這裡 題目會給定一個輸入整數x, 要求我們返回x的正整數平方根(取無條件捨去小數部分的正整數值)
這題基本上是前一題巴斯卡三角形的孿生題,那題和這題的本質是完全一樣的,只是題目要求稍有不同。 前一題求的是整個巴斯卡三角形,這一題求的是巴斯卡三角形的最後一層。
你可能也想看
Google News 追蹤
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
題目敘述 題目會給定我們兩個整數陣列作為輸入nums1, nums2,要求我們找出兩個陣列的差異值。 找出在nums1但是不在nums2的元素,以陣列的形式放在answer[0]輸出。 找出在nums2但是不在nums1的元素,以陣列的形式放在answer[1]輸出。 題目的原文敘述
Thumbnail
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,
Thumbnail
陣列可以說是最常見的資料結構,LeetCode 裡的題目有過半都和 Array 有關,因此也通常是解題新手的第一站。在第一篇專文,我們就從它的操作方法講起。
Thumbnail
題目會給我們一個方陣,要求我們計算兩條對角線的元素總和。
Thumbnail
題目會給定一個陣列,要求我們把裡面的數字依照奇偶數去排序, 偶數的排在前面,奇數的排在後面。
Thumbnail
👨‍💻簡介 陣列就像是一個儲存相同類型資料的容器,你可以想像成裝滿了一樣東西的盒子,每個東西都叫做陣列元素。這種類型可以是基本的,像是整數或字串,也可以是你自己定義的型別。不過陣列有個限制,就是大小一旦確定就無法改變。在Go語言裡,陣列的長度也是型別的一部分。
Linux shell 陣列 範例 1 : 重複執行同一件事 範例 2 : 檔案內容相似 , 只有部分需調整 範例 3 : 撈取字串轉存 陣列
海軍艦艇要裝哪種雷達可以反制匿蹤戰機,這是很好的科普資訊。 ★Ku波段,近迫武器用雷達,看得最清楚但人家已經衝到你面前了。方陣快砲用雷達。 ★X波段:F-35機身正面有大範圍匿蹤與雷達低可視度區,機尾也有一定範
Thumbnail
C# 陣列 – (C#教學) – Array為程式設計中最基本元素之一. 陣列就是用一個variable記下多個同類的值(記憶體中的位置), 以供日後所調用. 相關頁面: C# List – 學會List的5種基本應用方法 – 初始化, 加入值, 更新值, 刪除值, foreach迴圈
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
題目敘述 題目會給定我們兩個整數陣列作為輸入nums1, nums2,要求我們找出兩個陣列的差異值。 找出在nums1但是不在nums2的元素,以陣列的形式放在answer[0]輸出。 找出在nums2但是不在nums1的元素,以陣列的形式放在answer[1]輸出。 題目的原文敘述
Thumbnail
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,
Thumbnail
陣列可以說是最常見的資料結構,LeetCode 裡的題目有過半都和 Array 有關,因此也通常是解題新手的第一站。在第一篇專文,我們就從它的操作方法講起。
Thumbnail
題目會給我們一個方陣,要求我們計算兩條對角線的元素總和。
Thumbnail
題目會給定一個陣列,要求我們把裡面的數字依照奇偶數去排序, 偶數的排在前面,奇數的排在後面。
Thumbnail
👨‍💻簡介 陣列就像是一個儲存相同類型資料的容器,你可以想像成裝滿了一樣東西的盒子,每個東西都叫做陣列元素。這種類型可以是基本的,像是整數或字串,也可以是你自己定義的型別。不過陣列有個限制,就是大小一旦確定就無法改變。在Go語言裡,陣列的長度也是型別的一部分。
Linux shell 陣列 範例 1 : 重複執行同一件事 範例 2 : 檔案內容相似 , 只有部分需調整 範例 3 : 撈取字串轉存 陣列
海軍艦艇要裝哪種雷達可以反制匿蹤戰機,這是很好的科普資訊。 ★Ku波段,近迫武器用雷達,看得最清楚但人家已經衝到你面前了。方陣快砲用雷達。 ★X波段:F-35機身正面有大範圍匿蹤與雷達低可視度區,機尾也有一定範
Thumbnail
C# 陣列 – (C#教學) – Array為程式設計中最基本元素之一. 陣列就是用一個variable記下多個同類的值(記憶體中的位置), 以供日後所調用. 相關頁面: C# List – 學會List的5種基本應用方法 – 初始化, 加入值, 更新值, 刪除值, foreach迴圈