分類: 演算法/資料結構

Javascript 刷 LeetCode 學演算法 – 搜尋 Linear Search, Binary Search

Published on 由Sasa撰寫發表留言

Linear Search

時間複雜度：O(n)



744. Find Smallest Letter Greater Than Target


撞到語法不夠熟悉的問題，原本嘗試在 forEach 中 return 和 break，發現不適用
這種情況適合改用 for loop or every 等等其他方法，可參考以下文章

https://masteringjs.io/tutorials/fundamentals/foreach-break


Binary Search

時間複雜度： O log(n)

適用情境：在一個已排序的陣列中，找出其中特定的值

實作關鍵：遞迴or無窮迴圈，雙指標、中值
=> 設立雙指標、中值，並在查找的過程中不斷移動邊界

367. Valid Perfect Square

延伸閱讀：

取中值的公式

直觀來說會寫

int mid = (low + high)/2;

但這篇文章提到建議改寫

int mid = low + (high – low)/2;

原因是超過最大正整數時，會溢位，這時候取的中值就會是錯的

But if we calculate the middle index like this means our code is not 100% correct, it contains bugs.

That is, it fails for larger values of int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value(231 – 1 ).

The sum overflows to a negative value and the value stays negative when divided by 2.


Reference from geeksforgeeks

Javascript 刷 LeetCode 學演算法- 排序

Published on 由Sasa撰寫發表留言

在 Javascript 中遇到排序問題，通常可直接使用原生 function — sort()
因此很少自己實作排序的功能，此次透過刷題，嘗試用各種排序演算法，期待能更深入地對個演算法有記憶，並瞭解使用情境；相關的時間、空間複雜度，將會另撰寫文章

搭配相關的視覺化工具：VisualGo, VISUALIZE CODE EXECUTION
我個人是圖像化學習較能吸收，尤其在針對演算法這種較抽象的概念，能夠直觀地看逐步的過程，可以有更深入的理解。

摘要

將會用到的排序：

插入排序 Insert Sort
快速排列 Quick Sort (use space and in place )
堆排序 Bucket Sort

尋找第 K 個元素問題

  • LeetCode 215: Find Kth Elements
    思路：排序後即可求得
    實作：
    1. 使用 native sort 去排序 (LeetCode 實測結果: 80 ms, 39.2 MB)
    2. 實作 quick sort use space 去排序 (LeetCode 實測結果: 1432 ms, 182.5 MB)
    3. 實作 insert sort (LeetCode 實測結果: 612 ms, 41.2 MB)

其中在理解插入排序時，對於要用兩個迴圈這件事，我卡了好一陣子，直到查到這部影片，很生動地呈現，才頓悟，推薦給大家。
原來雙迴圈是使用了「雙指標」的概念：一個指標往前遍尋，一個指標往後遍尋。

//Topic: find Kth elements
//quick sort use space
var qsort = function(nums,k) {
if(nums.length <= 1) {
return nums
}
let leftAry = [];
let rightAry = [];
let pivot = nums[0];
for(let i = 1; i < nums.length ; i++){
nums[i] > pivot ? rightAry.push(nums[i]) : leftAry.push(nums[i])
}
return qsort(leftAry).concat(pivot, qsort(rightAry));
}
//native sort
var nativeSort = (nums,k) => {
nums.sort((a,b) => a-b)
return nums[nums.length – k]
}
const swap = (nums,a,b) => {
[nums[a],nums[b]] = [nums[b],nums[a]]
}
// insert sort
var insertSort = (nums,k) => {
for(let i = 1; i < nums.length; i++) {
let position = i;
while(position >= 0 && nums[position – 1] > nums[position]) {
swap(nums,position,position-1);
position–;
}
}
return nums[nums.length – k]
}
var findKthLargest = function(nums, k , sort) {
return sort(nums,k);
};
const nums = [3,2,1,5,6,4];
const k = 2;
console.log('qsort result:', findKthLargest(nums,k,qsort)[nums.length – k]);
console.log('nativeSort result:', findKthLargest(nums,k,nativeSort))
console.log('insertSort result:', findKthLargest(nums,k,insertSort))
view raw leetCode215.js hosted with ❤ by GitHub

=>動手試試

  • LeetCode 75: Sort Colors
    實作：
    1. 使用 quick sort use space 實作 sort (僅實作，題目要求要 in place)
    2. 使用 quick sort in place (原地實作，不另外佔空間)實作 sort (LeetCode 實測結果：68 ms, 39.8 MB)
    3. 使用 native sort (LeetCode 實測結果：68 ms, 39.8 MB)

同樣的我們可以先來看一支舞 XD

//use space
var sortColors1 = function(nums) {
const pivot = nums[0];
let left = [];
let right = [];
let i = 0;
while(i < nums.length -1) {
nums[i] < pivot ? left.push(nums[i]) : right.push(nums[i])
i++;
}
return […left,pivot,…right]
};
//native sort in js used quick sort when less data
var sortColorsNativeSort = (nums) => {
nums.sort((a,b) => a – b)
}
//implement quick sort in place
var swap = (list,a,b) => [list[a],list[b]] = [list[b],list[a]]
var getPointer = (nums,start,end) => {
const v = nums[start];
let pointer = start;
for(let i = start + 1; i < end ; i++){
if(nums[i] < v){
pointer++;
swap(nums,pointer,i);
}
}
swap(nums,start,pointer)
return pointer
}
const sortColors = (nums,start = 0,end = nums.length) => {
if(start >= end) return
const p = getPointer(nums,start,end)
sortColors(nums, start, p)
sortColors(nums, p+1, end)
}
const nums = [2,1,4,3,7,1,8]
sortColors(nums)
console.log(nums)
view raw leetCode75.js hosted with ❤ by GitHub

=>動手試試

  • LeetCode 347: Top K Frequent Elements
    思路：先排序再做堆
    學到： 善用 JS Map 型別，可以讓 code 更漂亮，以及 Object 與 Map 的差異，論 iterator 特性
var topKFrequent = function(nums, k) {
let hash = {}
nums.forEach(row => {
if(hash[row] === undefined) {
hash[row] = 1;
}else {
hash[row] += 1;
}
})
let res = […hash].sort((a,b) => a[1]-b[1])
//object can't iterator directory
console.log(res)
};
var topKFrequent2 = function(nums, k) {
let hash = new Map();
nums.forEach(row => {
if(hash.has(row)) {
hash.set(row,hash.get(row)+1);
}else {
hash.set(row,1);
}
})
console.log('hash key sort:');
for (var key of hash.keys()) {
console.log(key);
}
let res = […hash].sort((a,b) => b[1]-a[1])
res = res.map(item => item[0])
return res.slice(0,k)
};
const nums = [1,1,1,2,2,4], k = 2
console.log(topKFrequent2(nums,k))
view raw leetCode347.js hosted with ❤ by GitHub

=> 動手試試

延伸閱讀：

  1. 图解快速排序及双路三路快速排序

2. 各個瀏覽器對於 sort 的實作方式不同探討

Chrome engine v8 對於 Javascript 的 sort 實作：
基礎是用 Quick Sort 實作, 若陣列長度小於 10 則改用 Insert Sort 實作

The sorting algorithm itself is rather straightforward: The basis is a Quicksort with an Insertion Sort fall-back for shorter arrays (length < 10). The Insertion Sort fall-back was also used when Quicksort recursion reached a sub-array length of 10. Insertion Sort is more efficient for smaller arrays.

Reference from ChromeDoc
Reference: 淺談 JS sort() 到背後排序方法
Reference: 從 Array 的 sort 方法，聊到各瀏覽器的實作，沒想到 Chrome 和FireFox 的排序如此不同

謝謝你的閱讀，

以上是我的讀書筆記整理，歡迎各方大大討論交流校正～

喜歡的話， Medium 同步更新，歡迎前往拍手：）

我們下次見～