[用JS來寫演算法和了解資料結構] Day3 Data Structures - Array 陣列 - 簡易搜索、二分搜索、leetcode #1064

陣列

陣列應該是資料結構中對於寫javascript的人來說最友好的，js的陣列可以放入不同型別的資料(像是C/Java這樣的語言，陣列的大小和資料型別要先定義)，加上js有許多陣列方法，雖然蠻多是O(n^2)以上，但相對的寫法算很簡潔…

陣列像是編列好的一個置物櫃，有連續性(順序性)，要找某個櫃子只需要他的索引值index，array[index]陣列讀取時間複雜度O(1)。假設不知道索引值則是簡易搜尋O(n)像是使用for-loop。

Operations on Array

1. Insert - O(n) .unshift('a') - O(n) .push('a') - O(n)
2. Access - O(1) array[index]
3. Search - O(n)
4. Delete - O(n) .splice(2, 0, 'a') - O(n) .pop() - O(1)
5. Traverse
6. Sort

操作陣列的方法，之前有整理了一篇，忘記可以回去再看一下，這篇就不再次介紹

• 陣列方法筆記起來

Static & Dynamic Array

Static Array is fixed in size, you need to specify the number of elements your array will hold.
Dynamic Array is not fixed in size, you can append more elements.

陣列方法的時間複雜度，可以得知操作陣列最後一個元素都是O(1)，而操作第一個或中間某個因為會導致陣列的其他元素的位置都會改變，則變成O(n)。

簡易搜尋 / 線性搜索 Sequential Search / Linear Search - O(n)

1個耗費的步驟1次O(1) ，n個耗費的步驟就是n次O(n)，

• 把array中所有的數值都列出來
• 從一個沒有順序的array中找出某個元素，不知道index的情況下

function findNum(ary, target){
  for(let i = 0; i < ary.length; i++){
	  if(ary[i] === target){
	  	return true
	  }
  }
  return false
}

findNum([1,5,6,7,2], 2);

• 在一個沒有順序的array中找出最大或最小值

function findMax(ary) {
  let max;
  for (let i = 0; i < ary.length; i++) {
    if(max === undefined || max < ary[i]) {
      max = ary[i];
    }
  }
  return max;
}

findMax([1,5,6,7,2]);

找第二大

function findSecondMax(ary) {
  let max, second;
  for (let i = 0; i < ary.length; i++) {
    if(max === undefined || max < ary[i]) {
      second = max;
      max = ary[i];
    }else if(second === undefined || second < ary[i]){
      second = ary[i];
    }
  }
  return second;
}

findSecondMax([1,5,6,7,2]); // 6

二分搜尋 Binary Search - O(log n)

1個耗費的步驟1次O(1)，4個耗費的步驟為2次，n個耗費的步驟是log n次。

使用二分搜尋時，必須是一個排序好陣列(例如:A-Z，1-100，小到大，大到小)。在生活中最熟悉的例子就是終極密碼這個遊戲，小時候可能都有玩過。1-100猜一個數字，一開始大家都會先對半切 猜50，比50大還是比50小，知道比50小後再對半猜25，接下來以此類推。恩沒錯…這個就是二分搜尋的概念。

// ary = [5,17,33,41,55,61,80]
// target = 55

function binarySearch(ary, target){
  let low = 0;
  let high = ary.length - 1;
  let mid;
  let result = -1
  
  while(low <= high){
    mid = Math.floor((low + high) / 2);
    if(ary[mid] >= target){
      high = mid - 1;
      result = mid;
    }else{
      low = mid + 1;
	  }
  }
  return result;
}

binarySearch([5,17,33,41,55,61,80], 55);

• 若是陣列資料為字串可以先用 charCodeAt 轉成 UTF-16代碼值

let ary = ['Allen','Bill', 'Helen', 'Zoe'];
let aryCode = [];
ary.forEach((item, i) => {
  aryCode.push(item.charCodeAt(0));
})
console.log(aryCode); // [65, 66, 72, 90]

leetcode #1064 Fixed Point

• leetcode #1064 Fixed Point

題目:
Given an array A of distinct integers sorted in ascending order, return the smallest index i that satisfies A[i] == i. Return -1 if no such i exists.

給一個包含不同整數的陣列，排序由小到大，找出最小並符合A[i] == i的值。沒有符合的話回傳-1

Example 1:
Input: [-10,-5,0,3,7]
Output: 3
Explanation: 
For the given array, A[0] = -10, A[1] = -5, A[2] = 0, A[3] = 3, thus the output is 3.

Example 2:
Input: [0,2,5,8,17]
Output: 0
Explanation: 
A[0] = 0, thus the output is 0.

Example 3:
Input: [-10,-5,3,4,7,9]
Output: -1
Explanation: 
There is no such i that A[i] = i, thus the output is -1.
 
Note:
1 <= A.length < 10^4
-10^9 <= A[i] <= 10^9

 * @param {number[]} A
 * @return {number}
 */
var fixedPoint = function (A) {

}

//fixedPoint([-10, 1, 2, 3, 4, 5]); 
function fixedPoint(A){
  let low = 0;
  let high = A.length - 1;
  let mid;
  let minIndex = Infinity;

  while(low <= high){
    mid = Math.floor((low + high) / 2);
    if(A[mid] >= mid){
      high = mid - 1;
      minIndex = mid;
    }else{
      low = mid + 1;
    }
  }
  return minIndex === Infinity ? -1 : minIndex;
}

fixedPoint([-10,-5,0,3,7]); // 3
fixedPoint([0,3,7,8,10]); // 0
fixedPoint([-10,-5,3,4,7,9]); // -1
fixedPoint([-10, -5, 1, 3, 4, 5]); // 3
fixedPoint([-10, 1, 2, 3, 4, 5]); // 1

Codility - MinMaxDivision

題目：
You are given integers K, M and a non-empty array A consisting of N integers. Every element of the array is not greater than M.

You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.

The sum of the block from X to Y equals A[X] + A[X + 1] + … + A[Y]. The sum of empty block equals 0.

The large sum is the maximal sum of any block.

For example, you are given integers K = 3, M = 5 and array A such that:

  A[0] = 2
  A[1] = 1
  A[2] = 5
  A[3] = 1
  A[4] = 2
  A[5] = 2
  A[6] = 2
The array can be divided, for example, into the following blocks:

[2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
[2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
[2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
[2, 1], [5, 1], [2, 2, 2] with a large sum of 6.
The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.

Write a function:

function solution(K, M, A);

that, given integers K, M and a non-empty array A consisting of N integers, returns the minimal large sum.

For example, given K = 3, M = 5 and array A such that:

  A[0] = 2
  A[1] = 1
  A[2] = 5
  A[3] = 1
  A[4] = 2
  A[5] = 2
  A[6] = 2
the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

N and K are integers within the range [1..100,000];
M is an integer within the range [0..10,000];
each element of array A is an integer within the range [0..M].

學習與參考資料

• 前端工程師用 javaScript 學演算法
• Data Structures and Algorithms (DSA)
• Master the Coding Interview: Data Structures + Algorithms