75. Sort Colors

https://leetcode.com/problems/sort-colors/

Sort Colors - LeetCode

 

색상 정보(0,1,2) 3가지 목록이 주어졌을 때, 라이브러리를 사용하지 않고 정렬하는 문제다.

단순히 정렬이라 하길래 Quick sort로 구현을 했는데, 속도와 메모리 상으로 낮게 나오길래 Discuss를 통해 다른 사람의 답을 찾아보니 단순히 순환하며 low(0), mid(1), high(2)로 나누어 position을 계산하면서 swap해가는 방식으로 구현했더라..

---

이하 퀵정렬

class Solution { public:     int partition(vector<int>& nums, int left, int right) {         int low = left;         int high = right + 1;         int pivot = nums[left];         do         {             do {                 ++low;             } while (low < right && pivot > nums[low]);             do {                 --high;             } while (left < high && pivot < nums[high]);             if (low < high) {                 nums[low] ^= nums[high] ^= nums[low] ^= nums[high];             }         } while(low < high);         if (left != high) {             nums[left] ^= nums[high] ^= nums[left] ^= nums[high];         }         return high;     }     void quickSort(vector<int>& nums, int left, int right) {         if (left < right) {             int pivot = partition(nums, left, right);             quickSort(nums, left, pivot - 1);             quickSort(nums, pivot + 1, right);         }     }     void sortColors(vector<int>& nums) {         if (nums.size() <= 1) {             return;         }         quickSort(nums, 0, nums.size() - 1);     } };

---

---

이하 순차 swap

#define swap(x,y) ((x)^=(y)^=(x)^=(y)) class Solution { public:     void sortColors(vector<int>& nums) {         if (nums.size() <= 1) {             return;         }         int low = 0;         int mid = 0;         int high = nums.size() - 1;         while (mid <= high) {             switch(nums[mid]) {                 case 0: if (low != mid) swap(nums[low], nums[mid]); low++; mid++; break;                 case 1: mid++; break;                 case 2: if (mid != high) swap(nums[mid], nums[high]); high--; break;             }         }     } };

---

---

[Python3]

 

class Solution:     def sortColors(self, nums: List[int]) -> None:         if len(nums) <= 1:             return         low = 0         mid = 0         high = len(nums) - 1         while mid <= high:             if nums[mid] == 0:                 nums[low], nums[mid] = nums[mid], nums[low]                 low += 1                 mid += 1             elif nums[mid] == 1:                 mid += 1             elif nums[mid] == 2:                 nums[mid], nums[high] = nums[high], nums[mid]                 high -= 1

---