# 刷題筆記
:::info
**前言**
本筆記用來記錄刷NeetCode的過程。
:::
## 連結
* [NeetCode 150](https://neetcode.io/roadmap)
* [線上IDE](https://www.onlinegdb.com/)
* [線上畫流程圖工具](http://draw.io/)
## 1. Two Sum(Easy)
### 題目描述
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
* 2 <= nums.length <= 104
* -109 <= nums[i] <= 109
* -109 <= target <= 109
* Only one valid answer exists.
### 解題思路
* 方法一
* 把nums矩陣的數值兩兩配對看他們加起來是否等於target
* 方法二
* 建立一個長度為numsSize的Hash Table
* 取一個nums矩陣的數值，先算其complement(即target-數值)，再找看看complement有沒有存在於Hash Table，有的話表示找到答案，沒有的話則是把該數值新增到Hash Table中，再取下一個數值直到nums矩陣內容全都跑過一遍
### 程式碼
```c
// 方法一
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2; // 回傳值的矩陣大小固定是2
int *array = (int *)malloc(2*sizeof(int)); // 回傳值的矩陣大小固定是2
for (int i=0; i<numsSize; i++)
{
for(int j=1+i; j<numsSize; j++)
{
if(nums[i] + nums[j] == target)
{
array[0] = i;
array[1] = j;
return array;
}
}
}
return -1;
}
```
```c
// 方法二
typedef struct _hinfo
{
int idx;
int val;
} HASH_INFO;
typedef struct _hash_table
{
int size;
HASH_INFO *list;
} HASHER;
int Hash(HASHER *obj, int key)
{
// 用division method當作hash function
int r = key % obj->size;
// 矩陣的index不能是負的，所以key算出來的index如果是負數要做調整
int index = (r < 0) ? (r + obj->size) : (r);
return index;
}
int Hash_Find(HASHER *ht, int target)
{
int index = Hash(ht, target);
// 找到目標值的所在位置
while (ht->list[index].idx != -1)
{
if (ht->list[index].val == target)
{
return ht->list[index].idx;
}
index++;
index %= ht->size;
}
return -1;
}
void Hash_Add(HASHER *ht, int key, int idx)
{
int index = Hash(ht, key);
// 用linear probing方式處理衝突
while (ht->list[index].idx != -1)
{
index++;
index %= ht->size;
}
// 填入要新增的內容
ht->list[index].idx = idx;
ht->list[index].val = key;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2; // 回傳值的矩陣大小固定是2
int *indices = (int *)malloc(2*sizeof(int)); // 回傳值的矩陣大小固定是2
HASHER obj;
obj.list = malloc(sizeof(HASH_INFO)*numsSize);
obj.size = numsSize;
// 初始化把所有idx設為-1
for (int i = 0; i < numsSize; i++)
{
obj.list[i].idx = -1;
}
for (int i = 0; i < numsSize; i++)
{
int complement = target - nums[i];
// 如果目前的nums[i]數值其complement也存在於Hash表中，表示找到答案
// 如果其complement不存在於Hash表中，先把nums[i]存在Hash表中備用
int idx = Hash_Find(&obj, complement);
if (idx != -1)
{
indices = (int *) malloc(sizeof(int) * 2);
indices[0] = idx;
indices[1] = i;
*returnSize = 2;
break;
}
Hash_Add(&obj, nums[i], i);
}
free(obj.list);
return indices;
}
```
### 時間/空間複雜度
* 方法一:
* 時間複雜度: $O(n^2)$
* 空間複雜度: $O(1)$
* 方法二:
* 時間複雜度:
* 最好: $O(n)$，考慮到Hash Table的操作一般視為$O(1)$
* 最壞: $O(n^2)$，考慮到Hash_Find、Hash_Add內部while迴圈的worst-case
* [Hash table runtime complexity (insert, search and delete)](https://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete)
* 空間複雜度: $O(n)$
## 347. Top K Frequent Elements(Medium)
### 題目描述
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
* 1 <= nums.length <= 105
* -104 <= nums[i] <= 104
* k is in the range [1, the number of unique elements in the array].
* It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
### 解題思路
* 方法一:
* 建一個key-value表(key代表nums矩陣中的某數字，value是用來記錄該數字出現過的次數)
* 遍歷統計好nums矩陣內容的出現次數後，把表做從小到大的快速排序，並取出倒數k個內容組成矩陣作為返回值
* 方法二:
* 把nums矩陣的內容依序存進一個(用linked list處理衝突的)hash table
* 再用一個矩陣arr統計hash table各個index包含了多少linked list node(即該index曾發生過幾次衝突，即對應矩陣內容的出現頻率)
* 再把arr做從小到大的快速排序，並取出倒數k個內容組成矩陣作為返回值
### 程式碼
```c
// 方法一
#include <stdio.h>
#include <stdlib.h>
// 定義一個結構，儲存某數字和其出現頻率
struct KeyValuePair {
int key; // 某數字
int value; // 某數字在nums中出現的頻率
};
// qsort的比較函數，將使排序結果是按照頻率從小到大排序
int compare(const void* a, const void* b) {
return ((struct KeyValuePair*)a)->value - ((struct KeyValuePair*)b)->value;
}
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
// 建立一個固定長度的表，儲存某數值及其出現頻率
struct KeyValuePair* map = (struct KeyValuePair*)malloc(numsSize * sizeof(struct KeyValuePair));
// 初始化表
for (int i = 0; i < numsSize; i++) {
map[i].key = nums[i];
map[i].value = 0;
}
// 遍歷整個矩陣，統計矩陣內各數字的出現頻率
for (int i = 0; i < numsSize; i++) {
for (int j = 0; j < numsSize; j++) {
if (nums[i] == map[j].key) {
map[j].value++;
break;
}
}
}
// 使用快速排序讓表的內容按出現頻率從小到大排序
qsort(map, numsSize, sizeof(struct KeyValuePair), compare);
// 建立一個矩陣儲存前k個出現頻率最高的數字
int* result = (int*)malloc(k * sizeof(int));
// 將表中的倒數k個內容存在结果矩陣中
for (int i = 0; i < k; i++) {
result[i] = map[numsSize - i - 1].key;
}
*returnSize = k;
free(map);
return result;
}
```
### 時間/空間複雜度
* 方法一
* 時間複雜度: $O(n^2)$
* 空間複雜度: $O(n)$
## 128. Longest Consecutive Sequence(Medium)
### 題目描述
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
* 0 <= nums.length <= 105
* -109 <= nums[i] <= 109
### 解題思路
* 題目是要找出最長的子序列的長度。
* 先建一個hash table(HT)，把題目陣列中的元素全部存進去。
* 遍歷整個題目陣列，如果檢查到"當下元素的值-1"不存在於HT中，表示"當下元素的值"可視為一個子序列的起點，反之若不存在於HT中表示不能當作起點，故啥都不做。
* 如果有找到一個子序列的起點，就再檢查"當下元素的值+1"是否存在HT中，如果存在表示子序列長度可以加一，並且繼續檢查"當下元素的值+1+1"是否也存在HT中，如果存在表示子序列長度又可以加一，依此類推直到找不到下一個值，此時可以知道本次子序列的長度。
* 檢查本次子序列的長度是否為目前為止的最大值，是的話把最大值更新。
### 程式碼
```c
#include <stdio.h>
#define INIT_HASH_SIZE 4096
// 表示HT中的一個節點
typedef struct Hash
{
int key;
struct Hash *next; // 指向下一個節點的指標
} Hash;
// 初始化HT，返回一個指向HT的指標(陣列)
Hash **InitHash()
{
Hash **h = (Hash**)calloc(INIT_HASH_SIZE, sizeof(Hash*));
assert(h); // 確認h非空指標
return h;
}
// 建立一個新的HT節點，設定key值並返回該節點的指標
Hash *NewHash(int key)
{
Hash *h = (Hash*)malloc(sizeof(Hash));
assert(h); // 確認h非空指標
h->key = key;
h->next = NULL;
return h;
}
// 透過hash function計算HT索引
int HashKey(int key)
{
while(key < 0)
{
key += INIT_HASH_SIZE;
}
return (key % INIT_HASH_SIZE);
}
// 向HT添加一個節點，如果節點已存在則不重複增加(這樣就不會有衝突問題)
void AddHash(Hash **hash, int key)
{
assert(hash); // 確認hash非空指標
int hash_index = HashKey(key);
Hash **head = hash + hash_index;
if (!*head)
{
*head = NewHash(key);
}
else
{
Hash *h = *head;
while (h)
{
if (h->key == key)
{
return; // 節點已存在，不重复添加
}
else if (!h->next)
{
h->next = NewHash(key); // 在鏈表末尾添加節點
return;
}
h = h->next;
}
}
}
// 查找HT中是否存在特定key，存在返回1，否則返回0
int GetHash(Hash **hash, int key)
{
assert(hash); // 確認hash非空指標
Hash *h = hash[HashKey(key)];
while(h)
{
if (h->key == key)
{
return 1;
}
h = h->next;
}
return 0;
}
// 計算某個陣列中最長連續子序列的長度
int longestConsecutive(int* nums, int numsSize)
{
Hash **hash = InitHash();
int i, len, n, maxLen = 0;
// 把題目中的陣列內容添加到HT中
for (i = 0; i < numsSize; i++)
{
AddHash(hash, nums[i]);
}
// 遍歷陣列，計算最長連續子序列的長度
for (i = 0; i < numsSize; i++)
{
n = nums[i];
len = 1;
// 如果nums[i]-1不存在HT中，表示nums[i]是新的子序列的起點
if (GetHash(hash, n - 1) == 0)
{
// 如果nums[i]+1也存在HT中，表示連續子序列的計數值可加一
// 如果nums[i]+1+1也存在HT中，表示連續子序列的計數值又加一
// 如果nums[i]+1+1+1也存在HT中，表示連續子序列的計數值又加一
// 依此類推直到nums[i]+1+1...+1不存在HT中，表示這個新的子序列統計結束
while(GetHash(hash, ++n) == 1)
{
len++;
}
}
// 檢查這個新的子序列是否更長，更新最長連續子序列的長度
maxLen = (len > maxLen) ? len : maxLen;
}
return maxLen;
}
```
### 時間/空間複雜度
* 時間複雜度: $O(n)$
* 空間複雜度: $O(n)$
## 15. 3Sum(Medium)
### 題目描述
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
### 解題思路
* 類似two-sum的解法，這題可以先做好排序，再用for迴圈計算`0-num[i]`得到某個目標值
* 在`i`之後的陣列內容中，用頭尾兩個索引依序檢查有沒有加起來等於目標值的元素，有的話把這兩個元素連同`i`對應的元素存到結果陣列
* 依此類推直到找完輸入陣列的所有可能，將結果陣列作為返回值
* 如果輸入陣列有重複的元素，可以在運算途中跳過以增加執行效率
### 程式碼
```c
int compareInt(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
// 初始化結果陣列的容量
int cap = 32;
// 用於儲存結果的二維陣列
int **result = (int**)malloc(sizeof(int*) * cap);
// 用於儲存每個結果的列數
int *cols = (int*)malloc(sizeof(int) * cap);
// 暫存符合條件的三元組
int *triplet;
// 其他變數
int sum, target, count;
int i, left_index, right_index;
// 對輸入的陣列進行排序
qsort(nums, numsSize, sizeof(int), compareInt);
// 初始化結果計數器
count = 0;
// 輸入陣列從頭開始跑迴圈
// 迴圈會取陣列中的i、i+1、numsSize-1來檢查是否符合題目需求
for (i = 0; i < numsSize - 2; i++)
{
// 一旦數組中的i處元素大於0，
// 則不可能從後續的陣列內容中找出符合條件的三元組，
// 故跳出迴圈
if (nums[i] > 0)
{
break;
}
// 跳過相同值的元素，以避免生成重複的三元組
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
// 計算目標值
target = 0 - nums[i];
// 左索引初始位置
left_index = i + 1;
// 右索引初始位置
right_index = numsSize - 1;
// 在左索引超過右索引之前依序檢查其和是否會等於目標值
while (left_index < right_index)
{
sum = nums[left_index] + nums[right_index];
// 若和大於目標值，表示要改成加小一點的數字，故右索引向左移動
if (sum > target)
{
right_index--;
}
// 若和小於目標值，表示要改成加大一點的數字，故左索引向右移動
else if (sum < target)
{
left_index++;
}
// 若找到符合條件的三元組，將其存入結果陣列
else
{
triplet = (int*)malloc(sizeof(int) * 3);
triplet[0] = nums[i];
triplet[1] = nums[left_index];
triplet[2] = nums[right_index];
result[count] = triplet; // 存入結果陣列
cols[count] = 3; // 記錄列數
count++; // 結果計數器加一
// 若結果陣列容量不足，則擴展容量
if (count == cap)
{
cap *= 2;
result = (int**)realloc(result, sizeof(int*) * cap);
cols = (int*)realloc(cols, sizeof(int) * cap);
}
// 繼續尋找是否有其他組合可以讓和也等於目標值
left_index++;
right_index--;
// 跳過相同值的元素，避免生成重複的三元組
while(left_index < right_index &&
nums[left_index] == nums[left_index - 1])
{
left_index++;
}
while(left_index < right_index &&
nums[right_index] == nums[right_index + 1])
{
right_index--;
}
}
}
}
// 將結果數量存入returnSize
*returnSize = count;
// 將每個結果的列數存入returnColumnSizes
*returnColumnSizes = cols;
// 返回存儲結果的二維陣列
return result;
}
```
### 時間/空間複雜度
* 時間複雜度: $O(n^2)$
* 空間複雜度: $O(n)$
## 155. Min Stack(Medium)
### 題目描述
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
* `MinStack()` initializes the stack object.
* `void push(int val)` pushes the element val onto the stack.
* `void pop()` removes the element on the top of the stack.
* `int top()` gets the top element of the stack.
* `int getMin()` retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Example 1:
Input
```
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
```
Output
```
[null,null,null,null,-3,null,0,-2]
```
Explanation
```
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
```
Constraints:
* -2^31 <= val <= 2^31 - 1
* Methods pop, top and getMin operations will always be called on non-empty stacks.
* At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
### 解題思路
* 本題的目標是設計出一個stack(堆疊)物件，並且可以透過四個方法(push、pop、top、getMin)操作stack物件
* C語言可以用陣列當基礎實現stack資料結構
* 其中的push(int val)可以透過realloc擴大陣列長度，並在陣列最末端加入val來實現
* 其中的pop()可以透過縮短stack定義的size來間接實現(不用特地再調整陣列長度，把size值減1就好，這麼做不但符合需求又省時間)
* 其中的top()可以透過回傳當下陣列最末端的內容實現
* 其中的getMin()可以透過維護一個"最小值陣列"來實現，最小值陣列會在每次push的時候，更新當下stack內容的最小值到最小值陣列中。這樣未來呼叫getMin()時就可以快速得到stack在某個階段的最小值是多少
* 如果不用"最小值陣列"的作法，而是在每次呼叫getMin()時用一個for迴圈遍歷stack內容，會違反題目每個方法的時間複雜度都要是O(1)的要求
* 題目有限制呼叫四個方法的時候stack一定不是空的，故不用另外設計isEmpty()
### 程式碼
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int* data;
int* min;
int size;
} MinStack;
MinStack* minStackCreate()
{
MinStack* s = malloc(sizeof(MinStack));
s->data = NULL;
s->min = NULL;
s->size = 0;
return s;
}
void minStackPush(MinStack* obj, int val)
{
// 擴大stack和最小值陣列的空間
obj->data = realloc(obj->data, sizeof(int)*(obj->size + 1));
obj->min = realloc(obj->min, sizeof(int)*(obj->size + 1));
// 更新stack的內容
obj->data[obj->size] = val;
// 更新最小值陣列的內容
if(obj->size == 0 || obj->min[obj->size - 1] > val)
{
obj->min[obj->size] = val;
}
else
{
obj->min[obj->size] = obj->min[obj->size - 1];
}
// 更新size
obj->size++;
}
void minStackPop(MinStack* obj)
{
obj->size--;
}
int minStackTop(MinStack* obj)
{
return obj->data[obj->size - 1];
}
int minStackGetMin(MinStack* obj)
{
return obj->min[obj->size - 1];
}
void minStackFree(MinStack* obj)
{
free(obj->data);
free(obj->min);
free(obj);
}
int main()
{
MinStack* obj = minStackCreate();
minStackPush(obj, 11);
printf("stack top = %d ", minStackTop(obj));
printf("stack min = %d\n", minStackGetMin(obj));
minStackPush(obj, 22);
printf("stack top = %d ", minStackTop(obj));
printf("stack min = %d\n", minStackGetMin(obj));
minStackPush(obj, 33);
printf("stack top = %d ", minStackTop(obj));
printf("stack min = %d\n", minStackGetMin(obj));
minStackPush(obj, 4);
printf("stack top = %d ", minStackTop(obj));
printf("stack min = %d\n", minStackGetMin(obj));
minStackPush(obj, 55);
printf("stack top = %d ", minStackTop(obj));
printf("stack min = %d\n", minStackGetMin(obj));
return 0;
}
```
### 時間/空間複雜度
* 時間複雜度: 每個方法都是$O(1)$
* 空間複雜度: stack的空間$O(n)$
## 739. Daily Temperatures(Medium)
### 題目描述
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
* 1 <= temperatures.length <= 10^5
* 30 <= temperatures[i] <= 100
### 解題思路
* 題目是想找從"某天"開始算起，過了幾天後才變得更溫暖
* 建立並維護一個堆疊，堆疊內存放的是由以下兩者所組成的結構體(稱作pair)
* "還沒找到更溫暖日子"的"某天"
* "某天"對應的溫度
* 所以一旦找到更溫暖的日子，堆疊內的"某天"就會被pop掉並計算天數差值，再存入result陣列中的對應位置
### 程式碼
```c
#include <stdio.h>
#include <stdlib.h>
#define BOOL unsigned char
#define TRUE 1
#define FALSE 0
typedef struct
{
int day;
int temp;
} Pair;
typedef struct
{
Pair* data;
int size;
} Stack;
Stack* StackCreate()
{
Stack* s = malloc(sizeof(Stack));
s->data = NULL;
s->size = 0;
return s;
}
void StackPush(Stack* obj, Pair item)
{
// 擴大stack和最小值陣列的空間
obj->data = realloc(obj->data, sizeof(Pair)*(obj->size + 1));
// 更新stack的內容
obj->data[obj->size] = item;
// 更新size
obj->size++;
}
void StackPop(Stack* obj)
{
// 確認堆疊有內容
if(obj->size > 0)
{
obj->size--;
}
}
Pair StackTop(Stack* obj)
{
// 確認堆疊有內容
if(obj->size > 0)
{
return obj->data[obj->size - 1];
}
else
{
Pair emptyPair = {0, 0};
return emptyPair;
}
}
int GetStackTopDay(Stack* obj)
{
// 確認堆疊有內容
if (obj->size > 0)
{
return obj->data[obj->size - 1].day;
}
else
{
return 0;
}
}
int GetStackTopTemp(Stack* obj)
{
// 確認堆疊有內容
if (obj->size > 0)
{
return obj->data[obj->size - 1].temp;
}
else
{
return 0;
}
}
BOOL isStackEmpty(Stack* obj)
{
return (obj->size == 0);
}
void StackFree(Stack* obj)
{
free(obj->data);
free(obj);
}
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize)
{
// 建立一個堆疊
Stack* obj = StackCreate();
// 建立存放結果的陣列
// 變數result因為沒辦法free()，在LeetCode Submit時會跳"memory limit exceeded"
int* result = (int*) calloc(temperaturesSize, sizeof(int));
for (int i=0; i<temperaturesSize; i++)
{
int currentDay = i;
int currentTemp = temperatures[i];
// 如果堆疊有內容且當前溫度高於堆疊頂端的溫度
while(isStackEmpty(obj) == FALSE && currentTemp > GetStackTopTemp(obj))
{
// 讀取堆疊頂端的溫度，並從堆疊移除該溫度
int previousDay = GetStackTopDay(obj);
StackPop(obj);
// 更新天數差值
result[previousDay] = currentDay - previousDay;
}
// 把目前天數和溫度存入堆疊
Pair newPair = {currentDay, currentTemp};
StackPush(obj, newPair);
}
*returnSize = temperaturesSize;
StackFree(obj);
return result;
}
int main(void)
{
int temperatures[] = {73, 74, 75, 71, 69, 72, 76, 73};
int temperaturesSize = sizeof(temperatures) / sizeof(temperatures[0]);
int returnSize;
int* result = dailyTemperatures(temperatures, temperaturesSize, &returnSize);
printf("Result: ");
for (int i=0; i<returnSize; i++)
{
printf("%d ", result[i]);
}
printf("\n");
free(result);
return 0;
}
```
### 時間/空間複雜度
* 時間複雜度: $O(n^2)$
* 空間複雜度: $O(n)$
## 74. Search a 2D Matrix(Medium)
### 題目描述
You are given an m x n integer matrix `matrix` with the following two properties:
1. Each row is sorted in non-decreasing order.
2. The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
* m == matrix.length
* n == matrix[i].length
* 1 <= m, n <= 100
* -10^4 <= matrix[i][j], target <= 10^4
### 解題思路
* 因為題目提供的兩個特性，我們可以把原本的2D陣列視為一個1D有序排列的陣列，再用Binary Search查找target是否存在於此陣列中
### 程式碼
```c
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
int m = matrixSize;
int n = *matrixColSize;
int left = 0;
int right = m*n - 1;
int mid = left + (right - left)/2;
while (left <= right)
{
int row = mid / n;
int col = mid % n;
if (target < matrix[row][col])
{
right = mid - 1;
}
else if (target > matrix[row][col])
{
left = mid + 1;
}
else
{
return true;
}
mid = left + (right - left)/2;
}
return false;
}
```
### 時間/空間複雜度
* 時間複雜度: $O(log(m*n))$
* 空間複雜度: $O(1)$
<!--
## XXX. 模板(難度)
### 題目描述
### 解題思路
### 程式碼
```c
```
### 時間/空間複雜度
* 時間複雜度: $O()$
* 空間複雜度: $O()$
-->
Sign in with Wallet
Connect another wallet