前端程式員學好演算法系列（一）數組

前端程式員怎麼才能學好演算法呢？目前演算法優秀的視頻集中在c++，java，python，本人通過幾個月專心看c++的視頻掌握了演算法的基本思路，都翻譯成前端代碼一一寫出來，從真題到思維全面提升演算法思維
面對演算法面試，不畏懼

二分查找法O（logn）
尋找數組中的最大/最小值O(N)
歸併排序演算法 O（nlogn）
選擇排序演算法O(n^2)

第一題.數組 704.二分查找法

給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target  ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中並且下標為 4

解題：

1.在左邊界0 和右邊界arr.length -1 中進行尋找，

2.每次取最中間的元素mid，如果當前尋找的元素就是當前元素直接返回，

3.否則當前元素小於target左邊界等於mid+1 否則右邊界等於mid -1，如果沒有找到返回-1

 function binarySearch(arr,target) {
       let l = 0
       let r = arr.length - 1
       let mid
       while(l<=r){
          // mid = Math.floor((l + r)/2) 
          // 下麵的代碼解決l+r 整數溢出的問題
          mid = Math.floor(l + (r-l)/2) 
          
          if(arr[mid]===target){
             return mid
          }
          if(arr[mid] < target){
            l = mid + 1
          } else {
            r = mid - 1
          }
       }
       return -1
     }

第二題283. 移動零

給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
示例:

輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]

說明:

必須在原數組上操作，不能拷貝額外的數組。
儘量減少操作次數。

解題：

1.我們定義一個k指針預設為0
2.迴圈數組當數組值為0時交換數組k和當前索引的值k++
3.如果 i!=k 這步針對特殊用力優化

var moveZeroes = function(nums) {
        let k = 0
        for(let i =0;i<nums.length;i++){
          if(nums[i]){
            if(i!=k){
              swap(nums,k,i)
              k++
            } else {
              k++
            }
          }
        }
        function swap(arr,i,j){
          let tmp = arr[i]
          arr[i] = arr[j]
          arr[j] = tmp
        }
};

第三題 27.移動元素

給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等於 val 的元素，並返回移除後數組的新長度。

不要使用額外的數組空間，你必須僅使用 O(1) 額外空間並 原地 修改輸入數組。

元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

示例 1:

給定 nums = [3,2,2,3], val = 3,

函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。

你不需要考慮數組中超出新長度後面的元素。

解題：此題原理與上題相同

var removeElement = function(nums, val) {
    let j = 0
    let arr =[]
     for(let i =0,len=nums.length;i<len;i++){
         if(nums[i]!==val){ 
             nums[j] = nums[i]
             j++
         } 
     }
     return j
};

第四題 75. 顏色分類

給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顏色的元素相鄰，並按照紅色、白色、藍色順序排列。

此題中，我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。

註意:
不能使用代碼庫中的排序函數來解決這道題。

示例:

輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]

解題一
暴力解法：
1.本題只有三種顏色所以我們可以給統計每個元素出現的次數保存起來然後在按數量值依次排列，代碼如下

var sortColors = function(nums) {
    let obj = {}
    for(let i =0;i<nums.length;i++){
        if(!obj[nums[i]]){
            obj[nums[i]] = 1
        } else {
            obj[nums[i]] = obj[nums[i]] + 1
        }
    }
    let index = 0
    for(let i=0;i<obj[0];i++){
        nums[index++] = 0
    }
    for(let i=0;i<obj[1];i++){
        nums[index++] = 1
    }
    for(let i=0;i<obj[2];i++){
        nums[index++] = 2
    }
};

解法二

三路快排

1.定義前邊界zero為-1，因為預設左邊界中沒有任何一個元素，左邊界記憶體放所有為0的元素
2. 定義右邊界tow後面的元素都是2，tow中預設也不存在任何元素
3.我們這裡for迴圈時沒有i++ 因為我們需要處理一種不需要i++的情況，噹噹前願隨num[i] ==2時我們把 tow-- 然後tow和i交換位置，此時i位置的元素為tow位置交換過去的元素，還為訪問，所以i不需要++

var sortColors = function(nums) {
     let zero = -1     // nums[0...zero] ==0
     let tow = nums.length // nums[tow..n-1] ==2
     for(let i =0;i<tow;){
         if(nums[i]===1){
             i++
         } else if(nums[i] ==2){
             --tow
            swap(nums,i,tow)
         } else {
            zero++
            swap(nums,i,zero)
            i++
         }
     }
    function swap(arr,i,j){
        let tmp =arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
    }
};

演算法數組入門暫時就先寫到這裡