Leetcode Problem:
Summary
- Given an array of integers and a pivot value, rearrange the array such that all elements less than the pivot appear before all elements greater than the pivot, and elements equal to the pivot appear in between.
Approach
- Separate the array into three lists: less than pivot, equal to pivot, and greater than pivot
- Then, concatenate these lists to form the rearranged array.
Complexity
- O(n), where n is the number of elements in the array
- This is because each element in the array is visited once.
Explanation
- This solution uses three lists to separate the array into three categories based on the pivot value
- Then, it concatenates these lists to form the rearranged array
- This approach ensures that all elements less than the pivot appear before all elements greater than the pivot, and elements equal to the pivot appear in between
- The time complexity is O(n) because each element in the array is visited once.
Solution Code:
class Solution {
public:
vector pivotArray(vector& nums, int pivot) {
vector less;
vector equal;
vector greater;
for(int i = 0 ; i < nums.size(); i++){
if(nums[i] < pivot){
less.push_back(nums[i]);
} else if(nums[i] > pivot){
greater.push_back(nums[i]);
} else{
equal.push_back(nums[i]);
}
}
vector ans;
ans.insert(ans.end(), less.begin(), less.end());
ans.insert(ans.end(), equal.begin(), equal.end());
ans.insert(ans.end(), greater.begin(), greater.end());
return ans;
}
};
'알고리즘' 카테고리의 다른 글
| Minimum Number of Operations to Move All Balls to Each Box (0) | 2025.03.04 |
|---|---|
| Shifting Letters II (0) | 2025.03.04 |
| Number of Ways to Split Array (0) | 2025.03.03 |
| Count Vowel Strings in Ranges (0) | 2025.03.03 |
| Minimum Cost For Tickets (0) | 2025.03.03 |
짬뽕얼큰하게
