contributed by < [tintinjian12999](https://leetcode.com/tintinjian12999/) >
# Sorting
## [LeetCode #88 Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/)
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
```
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
```
如果想著要從小的地方開始 merge 的話就會有很多要考慮的 case，建議從大的地方開始 merge，我們已經知道 nums1 裡有效資料的範圍 m 和 nums2 的資料長度 n，總長度為 m + n，因此我們要做的便是比較 nums1 的第 m - 1 個資料(從0開始算)與 nums2 的第 n - 1 個資料的大小，並將較大的一方放入 nums1 的第 m + n - 1 格(因為 nums1 只有 m 個有效資料因此可以直接放入而不會影響到後續的運算)，放入資料後需要將索引 - 1 繼續往小的比較，要放入的位置也要 - 1。 若到最後 nums2 還有剩下的元素則依據大小填入 nums1 剩下的空間裡(若是 nums1 還有剩下元素則不需做處理)，最後回傳 nums1 矩陣。
以 Example1 為例，m = 3， n = 3，比較 3 和 6 這兩個元素發現 6 > 3 ，因此將 6 放入 nums1 的第 5 格，此時的 nums1 為 [1, 2, 3, 0, 0, 6]，接著比較 5 和 3 並依此類推。
以下是 C 的實作
```c
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] >= nums2[j]) {
nums1[k] = nums1[i];
i--;
k--;
}
else if (nums1 [i] < nums2[j]) {
nums1[k] = nums2[j];
j--;
k--;
}
}
while (j >= 0) {
nums1[k] = nums2[j];
j--;
k--;
}
```
**時間複雜度:O(m + n)**
## [LeetCode #274 H-Index](https://leetcode.com/problems/h-index/)
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
```
Example 1:
Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
```
根據 [H-Index 的定義](https://en.wikipedia.org/wiki/H-index)，我們要找的是至少有 h 篇論文被引用超過 h 次，基本上最直觀的做法就是將輸入資料由大到小排序，並新增一個計數器 count ，在走訪輸入陣列的過程中逐步遞增 count 的值，直到 count 大於或等於陣列內的值時回傳當時的 count，此時的 count 即為 H-Index。
以 Example 1 為例，將輸入陣列由大到小排列後為 [6, 5, 3, 1, 0]，接著令 count 為 0 從第 0 個元素開始走訪，所對應到的 count 為 [0, 1, 2, 3, 4, 5]，可以發現當 count = 3 的時候滿足 H-Index的需求，有三篇的 cite 至少為 3 次。
以下是 C 的實作
```c
int cmp( const void *a, const void *b) {
return *((int*) b) - *((int*) a) ;
}
int hIndex(int* citations, int citationsSize){
qsort(citations, citationsSize, sizeof(int), cmp);
int count = 0;
int i = 0;
for (int i = 0; i < citationsSize; i++) {
if (count >= citations[i])
break;
count++;
}
return count;
}
```
**時間複雜度:O(nlgn) + O(n) (排序加上走訪)**
# Search
## [LeetCode #852 Peak Index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/)
An array arr a mountain if the following properties hold:
arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].
You must solve it in O(log(arr.length)) time complexity.
```
Example 1:
Input: arr = [0,1,0]
Output: 1
Example 2:
Input: arr = [0,2,1,0]
Output: 1
Example 3:
Input: arr = [0,10,5,2]
Output: 1
```
使用 binary search 可以用遞迴和迭代解這題
### 遞迴:
因為是山形陣列，只會有一個最大值，所以只要看切割到的點在遞增、遞減、或者是頂點就行，遞增代表頂點在右邊，遞減代表頂點在左邊，如下圖所示
因此只要看取到的點與其前後兩個點的關係再繼續作分割即可，以下是 C 的實作
```c
int binary_search(int* arr, int lower, int upper)
{
int middle = (lower + upper) >> 1;
if (arr[middle] > arr[middle + 1] && arr[middle] > arr[middle - 1]) {
return middle;
} else if (arr[middle + 1] >= arr[middle] ) {
return binary_search(arr, middle, upper);
} else {
return binary_search(arr, lower, middle);
}
return -1;
}
int peakIndexInMountainArray(int* arr, int arrSize){
return binary_search(arr, 0, arrSize - 1);
}
```
### 迭代
迭代法的想法是在迴圈執行的過程中改變 lower 與 upper 兩數的值，若為遞增則將新的 lower 設為 中點加一，反之則將新的 upper 設為中點減一，重複直到 middle 為頂點為止。
以下是 C 的實作
```c
int binary_search(int* arr, int lower, int upper)
{
while (upper >= lower) {
int middle = lower + (upper - lower) / 2;
if (arr[middle] > arr[middle + 1] && arr[middle] > arr[middle - 1])
return middle;
else if (arr[middle + 1] >= arr[middle])
lower = middle + 1;
else
upper = middle - 1;
}
return -1;
}
int peakIndexInMountainArray(int* arr, int arrSize){
return binary_search(arr, 0, arrSize - 1);
}
```
## [LeetCode #35 Search Insert Position](https://leetcode.com/problems/search-insert-position/)
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
```
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
```
要找出該把 target 插入在哪，且要滿足 O(lgn)，可以用 binary search 做。
想法與上方的迭代法很像，切出 middle 後，在過程中用 position 計算目前的 middle 值，如果 middle 所在的元素比 target 小則讓新的 upper = middle - 1、position = middle，反之則讓 lower = middle + 1、position = middle + 1，當 lower 和 upper 相遇時 position 的值即為要插入的位置。
以下是 C 的實作
```c
int iterative_binary_search(int* nums, int lower, int upper, int target)
{
int position;
while (upper >= lower) {
int middle = lower + (upper - lower) / 2;
if (nums[middle] == target)
return middle;
else if (nums[middle] > target) {
position = middle;
upper = middle - 1;
} else {
position = middle + 1;
lower = middle + 1;
}
}
return position;
}
```
## [LeetCode #278 First Bad Version](https://leetcode.com/problems/first-bad-version/)
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
```
Example 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
Example 2:
Input: n = 1, bad = 1
Output: 1
```
其實都大同小異，先用 middle 分割，再視情況選擇新的 upper 與 lower
```c
int binary_search(int lower, int upper)
{
while (lower <= upper) {
int middle = lower + (upper - lower) / 2;
bool bad = isBadVersion(middle);
if (bad) {
upper = middle - 1;
} else {
lower = middle + 1;
}
}
return lower;
}
int firstBadVersion(int n) {
return binary_search(1, n);
}
```
## [LeetCode #441 Arranging Coins](https://leetcode.com/problems/arranging-coins/)
You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.
Given the integer n, return the number of complete rows of the staircase you will build.
```
Example 1:
Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.
```
```
Example 2:
Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.
```
透過連加的公式解可以得知把 n 層填滿需要 n * (n + 1) / 2 個硬幣，可以用這個當基準去做 binary search。
```c
int binary_search(long long lower, long long upper, int n)
{
while (lower <= upper) {
long long middle = (lower + upper) / 2;
long long sum = middle * (middle + 1) / 2;
if (sum == n)
return middle;
else if (sum < n) {
lower = middle + 1;
} else if (sum > n) {
upper = middle - 1;
}
}
return lower - 1;
}
int arrangeCoins(int n){
return binary_search(1, 2 * sqrt(n), n);
}
```
# Divide and Conquer
## [LeetCode #53 Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)
Given an integer array nums, find the subarray with the largest sum, and return its sum.
```
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
```
詳情看書
以下是 c++ 的實作
```cpp
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
if (len == 0) {
return -2147483648;
}
if (len == 1) {
return nums[0];
}
int middle = len >> 1;
vector<int> data_left(nums.begin(), nums.begin() + middle);
vector<int> data_right(nums.begin() + middle, nums.end());
int max_left = maxSubArray(data_left);
int max_right = maxSubArray(data_right);
int max_center = maxCrossArray(nums);
if (max_left >= max_center && max_left >= max_right) {
return max_left;
} else if (max_right >= max_center && max_right >= max_left) {
return max_right;
} else {
return max_center;
}
}
int maxCrossArray(vector<int>& nums) {
int len = nums.size();
int mid = (len - 1) / 2;
int center = nums[mid];
int max_left = -2147483648;
int max_right = -2147483648;
int sum = 0;
for (int i = mid - 1; i >= 0; i--) {
sum += nums[i];
if (sum > max_left) {
max_left = sum;
}
}
if (max_left > 0) {
center += max_left;
}
sum = 0;
for (int i = mid + 1; i < len; i++) {
sum += nums[i];
if (sum > max_right) {
max_right = sum;
}
}
if (max_right > 0) {
center += max_right;
}
return center;
}
};
```
**時間複雜度:O(nlgn)**
比較快的作法 (抄來的)，但我覺得沒有很嚴謹，先隱藏
:::spoiler
```cpp
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int cur_sum = 0;
int max_sum = nums[0];
for (int i = 0; i < nums.size() ; i++) {
cur_sum += nums[i];
if (cur_sum > max_sum)
max_sum = cur_sum;
if (cur_sum < 0)
cur_sum = 0;
}
return max_sum;
}
};
```
**時間複雜度:O(n)**
:::
## 選擇問題
參考 [30讀書會](https://hackmd.io/@30life-algorithm/BJxN1tOSs) 的想法，以下分段解釋
首先是 median function 用來找出中位數和 MOM
```cpp
int median(vector<int>& nums, int len, int position)
{
sort(nums.begin() + position, nums.begin() + position + len);
return nums[position + len / 2];
}
```
```cpp
if (len <= 4) {
sort(nums.begin(), nums.end());
return nums[k];
}
```
如果長度小於 5 (因為 5 個為一組)則直接回傳第 k 個，
```cpp
for (i = 0; i < len / 5; i++) {
med.push_back(median(nums, 5, i * 5));
}
if (i * 5 < len) {
med[i] = median(nums, len % 5, i * 5);
}
int MOM = selection(med, med.size() / 2, med.size());
```
將陣列五個分為一組並取出各組的中位數，MOM 求法可以透過將 med 矩陣遞迴並選擇第 k / 2 大的元素獲得 (也就是 med 這個矩陣的中位數)。
```cpp
vector<int> X2;
vector<int> X1;
for (int i = 0; i < len; i++) {
if (nums[i] > MOM)
X2.push_back(nums[i]);
else
X1.push_back(nums[i]);
}
```
用 X2 儲存大於 MOM 的元素， X1 儲存小於 MOM
```cpp
int X2_len = X2.size();
if (X2_len == (k - 1))
return MOM;
if (X2_len > (k - 1))
return selection(X2, k, X2_len);
return selection(X1, k - X2_len - 1, X1.size());
```
第迴直到 MOM 就是要找的那個元素。
完整程式碼
:::spoiler
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int median(vector<int>& nums, int len, int position)
{
sort(nums.begin() + position, nums.begin() + position + len);
return nums[position + len / 2];
}
int selection(vector<int>& nums, int k, int len)
{
int i = 0;
if (len <= 4) {
sort(nums.begin(), nums.end());
return nums[k];
}
vector<int> med;
for (i = 0; i < len / 5; i++) {
med.push_back(median(nums, 5, i * 5));
}
if (i * 5 < len) {
med[i] = median(nums, len % 5, i * 5);
}
int MOM = selection(med, med.size() / 2, med.size());
vector<int> X2;
vector<int> X1;
for (int i = 0; i < len; i++) {
if (nums[i] > MOM)
X2.push_back(nums[i]);
else
X1.push_back(nums[i]);
}
int X2_len = X2.size();
if (X2_len == (k - 1))
return MOM;
if (X2_len > (k - 1))
return selection(X2, k, X2_len);
return selection(X1, k - X2_len - 1, X1.size());
}
int main()
{
vector<int> nums = {5, 4, 3, -2, 1, -4, 1};
cout << selection(nums, 3, nums.size()) << endl;
system("pause");
return 0;
}
```
:::
## [LeetCode #169 Majority Element](https://leetcode.com/problems/majority-element/)
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
```
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
```
將陣列分為兩半，並遞迴，回傳子陣列中的主要元素，若兩邊的主要元素相等回傳，若不相等則比較兩邊主要元素出現的次數並回傳次數大的那個。
```c
int majorityElement(int* nums, int numsSize){
if (numsSize == 1)
return nums[0];
int middle = (numsSize) / 2;
int left_max = majorityElement(nums, middle);
int right_max = majorityElement(nums + middle, numsSize - middle);
if (left_max == right_max) {
return left_max;
}
int left_count = 0;
int right_count = 0;
for (int i = 0; i <= middle; i++)
if (nums[i] == left_max)
left_count++;
for (int i = middle + 1; i < numsSize; i++)
if (nums[i] == right_max)
right_count++;
return (left_count > right_count) ? left_max:right_max;
}
```
## [LeetCode #240 Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/)
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
```
Example 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
Example 2:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false
```
從右上角開始搜尋的時候，如果要搜尋的元素比最右上的元素大的話，該元素只會存在於最右上元素以下的橫列，也就能將搜尋的範圍縮小為最右上元素下方的子陣列，如果比最右上的元素小的話，該元素只會存在於最右上元素左方的直列，就能將搜尋範圍縮小為最右上元素左方的子陣列。
```c
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
int ini_row = 0;
int ini_col = *matrixColSize - 1;
while (ini_row < matrixSize && ini_col >= 0) {
if (target == matrix[ini_row][ini_col]) {
return true;
} else if (target > matrix[ini_row][ini_col]) {
ini_row++;
} else
ini_col--;
}
return false;
}
```
Sign in with Wallet
Connect another wallet