作業三題解
===
###### tags: `成大演算法春季課程`
## [Sort the array!](https://judge.ccns.io/problems/8)
- Task Provider: 參考 [Leetcode : 912. Sort an Array](https://leetcode.com/problems/sort-an-array/)
- Task Setter: joey3639570
### 解法說明
根據題目要求：
> 順帶一提，老師在這裡要的排序方程式有以下要求：
> - 大多數的時候希望有 $O(n\log(n))$ 的時間複雜度，
> - 在 Worst Case 的時候不該是 $n^2$ 的時間複雜度
按題目所敘述的話是盡量不要使用 **Quicksort** 即可，
提到 sort 很多人的第一反應是直接使用 `std::sort`
在此希望各位去看看 `std::sort` 的細節，
至少要知道自己所用的函式內容為何，及其於各 Case 的表現。
>**Algorithms used by sort()**
The algorithm used by sort() is **IntroSort**. Introsort being a **hybrid sorting algorithm** uses three sorting algorithm to minimize the running time, **Quicksort, Heapsort and Insertion Sort**. Simply putting, it is the best sorting algorithm around. It is a hybrid sorting algorithm, which means that it uses more than one sorting algorithms as a routine.
參考連結: [Internal details of std::sort() in C++](https://www.geeksforgeeks.org/internal-details-of-stdsort-in-c/)
### 參考解答
在此我使用 HeapSort 解決此排序問題。
| Case | Complexity |
|:-------:|:----------:|
| Worst | $O(nlogn)$ |
| Best | $O(nlogn)$ |
| Average | $O(nlogn)$ |
```cpp=
#include <iostream>
#define SIZE 50000
using namespace std;
int n, arr[SIZE];
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
cin >> n;
for(int i=0; i<n; i++){
cin >> arr[i];
}
heapSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
## [min-heapify](https://judge.ccns.io/problems/8)
- Task Provider: 課本講義
- Task Setter: joey3639570
### 解法說明
此題目的只是為了看各位對於課本講義上的理解，
講義上提供的例子為 Max-heapify ，
Pseudo Code 如下:
此題須注意的是 level order 的部分，
如同同學一開始指出的，**一個一個放入樹，且保持 min-heap** 與 **都先放入樹，再將樹建立成 min-heap** 是不同的。
本題要求的是後者。
### 參考解答
```cpp=
#include <iostream>
#define SIZE 1025
int n, arr[SIZE];
using namespace std;
void min_heapify(int *a,int i,int N)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= N)
{
if (j < n && a[j+1] < a[j])
j = j + 1;
if (temp < a[j])
break;
else if (temp >= a[j])
{
a[j/2] = a[j];
j = 2 * j;
}
}
a[j/2] = temp;
return;
}
void build_minheap(int *a, int N)
{
int i;
for(i = N/2; i >= 1; i--)
{
min_heapify(a,i,N);
}
}
int main()
{
int i;
cin>>n;
for (i = 1; i <= n; i++)
{
cin>>arr[i];
}
build_minheap(arr, n);
for (i = 1; i <= n; i++)
{
cout << arr[i] << " ";
}
}
```
## [Smallest Range Covering Elements from k Lists](https://judge.ccns.io/problems/10)
- Task Provider: 參考 [Leetcode : 632. Smallest Range Covering Elements from K Lists](https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/)
- Task Setter: joey3639570
### 解法說明
此題為 heap 的應用延伸，
當然其他作法跟解法很多，但這裡以會以 min-heap 解法為主，
使用 min-heap 的原因是避免多次搜尋最小值影響時間，
在這邊助教沒設定好測資跟時間的大小，可能會導致有時間內但 TLE 的狀況發生，但其實可能是 SE 或其他錯誤。
解題邏輯:
- 由於我們知道每個 list 都是非遞減排列，list 的開頭第一個元素應該是該 list 的最小元素。
- 既然要的是每個 List 都要 cover 到的範圍，從 list 內取出的值會是最貼合範圍的取法。
- 在這裡我們使用取最小範圍的方法是
- 利用 min_heap 紀錄當前最小元素。
- 以比較的方式隨時知道當前最大元素。
- 範圍為**最大元素 - min_heap 最前端的元素 + 1**
### 參考解答
在這裡我使用 `priority_queue` 協助我建立一個好操作的 min-heap ，存放於內的元素為 `pair<int,pair<int,int>>` ，詳細使用說明請參考以下:
- [std::priority_queue](https://www.cplusplus.com/reference/queue/priority_queue/)
- [How to implement Min Heap using STL?](https://www.geeksforgeeks.org/implement-min-heap-using-stl/)
```cpp=
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
vector<int> smallestRange(vector<vector<int>>& nums) {
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>pq;
int mx=INT_MIN;
int cans=INT_MAX;
int lo=INT_MIN,hi=INT_MAX;
for(unsigned int i=0;i<nums.size();i++)
{
mx=max(mx,nums[i][0]);
pq.push({nums[i][0],{i,0}});
}
while(!pq.empty())
{
auto x=pq.top();
pq.pop();
int na=mx-x.first+1;
if(cans>na)
{
cans=na;
lo=x.first;
hi=mx;
}
if(x.second.second>=nums[x.second.first].size()-1)
break;
pq.push({nums[x.second.first][x.second.second+1],{x.second.first,x.second.second+1}});
mx=max(mx,nums[x.second.first][x.second.second+1]);
}
return {lo,hi};
}
int main () {
int n, k, a;
cin >> n;
std::vector<vector<int>> wholevector;
for (int i=0;i<n;i++) {
cin >> k;
vector<int> tmpvector;
for (int j=0;j<k;j++) {
cin >> a;
tmpvector.push_back(a);
}
wholevector.push_back(tmpvector);
}
vector<int> result = smallestRange(wholevector);
for (size_t i = 0; i < result.size(); ++i) {
cout << result[i] << " ";
}
return 0;
}
```
Sign in with Wallet
Connect another wallet