陣列操作入門題 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

avatar-img
88會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目會給定一個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
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
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
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
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迴圈