ปัญหา
จัดเรียง array ให้เลขคู่ (even) อยู่หน้า เลขคี่ (odd) อยู่หลัง
ตัวอย่าง: [1,5,6,8,7,2,3] → [6,8,2,5,7,1,3] (ลำดับภายในกลุ่มไม่สำคัญ)
วิธีแก้: Two Pointers (Partition แบบ Quick Sort)
อัลกอริทึม
- i = 0 (ตำแหน่งสำหรับ even ถัดไป), j = 0 (current)
- While j < n:
- ถ้า arr[j] เป็นเลขคู่: swap arr[i] และ arr[j], i++
- j++
- คืนค่า arr
โค้ด Python
class Solution:
def sortArrayByParity(self, a):
i = 0
j = 0
while j < len(a):
if a[j] % 2 == 0:
a[i], a[j] = a[j], a[i]
i += 1
j += 1
return a
# ทดสอบ
ob = Solution()
print(ob.sortArrayByParity([1, 5, 6, 8, 7, 2, 3])) # [6, 8, 2, 5, 7, 1, 3] (order may vary)
print(ob.sortArrayByParity([0, 1, 2, 3, 4])) # [0, 2, 4, 1, 3]
print(ob.sortArrayByParity([])) # []
print(ob.sortArrayByParity([2, 4, 6])) # [2, 4, 6]
ความซับซ้อน
- Time: O(n) - single pass
- Space: O(1) - in-place
วิธีอื่นๆ
1. List Comprehension (ไม่ in-place)
def sortArrayByParity(self, a):
return [x for x in a if x % 2 == 0] + [x for x in a if x % 2 == 1]
2. Sort with Key
def sortArrayByParity(self, a):
return sorted(a, key=lambda x: x % 2)
3. Two Pointers จากสองข้าง (Swap ends)
def sortArrayByParity(self, a):
left, right = 0, len(a) - 1
while left < right:
if a[left] % 2 == 0:
left += 1
elif a[right] % 2 == 1:
right -= 1
else:
a[left], a[right] = a[right], a[left]
left += 1
right -= 1
return a
เปรียบเทียบ
| วิธี | Time | Space | In-place | Stable |
|---|---|---|---|---|
| Two pointers (single pass) | O(n) | O(1) | Yes | No |
| List comprehension | O(n) | O(n) | No | Yes |
| Sorted with key | O(n log n) | O(n) | No | Yes |
| Two pointers (two ends) | O(n) | O(1) | Yes | No |
LeetCode 905: Sort Array By Parity
โจทย์คลาสสิก - ต้องการ in-place O(n) solution
