算法學習(三): 數(shù)組

數(shù)組的基本概念

定義:

通常由一組相同類型的元素的集合所組成的結(jié)構(gòu)(javascript允許數(shù)組中包含不同類型的元素)
計算機會分配一塊連續(xù)的內(nèi)存來存儲這個元素集合
利用索引可以取出元素對應的存儲地址

特性:

在內(nèi)存中為連續(xù)空間
定址公式: addr(curElem)=addr(intialElem)+sizeof(curElem)*index
通過index獲取數(shù)組元素的時間復雜度為O(1)
通常數(shù)組第一個位置的索引是0

數(shù)組示意圖如下:

在java中可以這么定義一個數(shù)組

int[] array = {2,4,5,6,22,89,35} //定義數(shù)組

array[1] // 值為4 取出索引1位置的值
array[5] // 值為89 取出索引5位置的值

我們還可以定義二維數(shù)組

int[][]  array={{1,2,3},{66,45,33,4},{2,7,8}}

三維數(shù)組也是可以定義的, 這里就不舉例了

為什么使用數(shù)組

簡化代碼, 提高效率
將相同類型的元素組織在一起

比如, 我們要存1-1000這1000個數(shù), 用數(shù)組就能很簡單的存儲, 并且由于數(shù)組的每一個元素都是連續(xù)開辟的內(nèi)存空間, 所以也能快速的取到中間任意的值

int[] nums = new int[1000];
for(int i=0; i<nums.length;i++) {
  nums[i] = i+1;
}

nums[5] //6
nums[926] //927

常見數(shù)組算法題

因為我自己比較熟悉js, 所以關(guān)于算法題的代碼, 我都用js代碼寫, 當然我也只是個初學者, 所以大家不要糾結(jié)我代碼寫的好不好看, 主要看解題思路就好了

例1: 兩數(shù)之和

給定一個整數(shù)數(shù)組(無重復元素)和一個目標值, 找出數(shù)組中和為目標值的兩個數(shù)。
按照從小到大的順序輸出結(jié)果對
將所有結(jié)果對輸出到一個數(shù)組
例:
Input: number = {2,7,11,15}, target = 9

Output: {2,7}

分析需求:

數(shù)組是否排序
有沒有重復元素
結(jié)果是返回全部還是返回任意一個

解題思路:

思路1：
暴力解法來解

function twoSum(arr, target) {
  let result = []
  let index = 0 
  if(arr.length < 2) {
    return result
  }
  for(let i=0; i<arr.length; i++) {
    for(let j=i+1; j<arr.length; j++) {
      if(arr[i] + arr[j] === target) {
        if(arr[i] < arr[j]) {
          result[index] = []
          result[index].push(arr[i])
          result[index].push(arr[j])
          index++
        }else {
          result[index] = []
          result[index].push(arr[j])
          result[index].push(arr[i])
          index++
        }

      }
    }
  }
  return result
}

let newArray = twoSum([1,3,4,5,6,8,78], 9)
console.log(newArray)

思路1總結(jié):

時間復雜度O(n²)
存在無意義操作
例如:
78已經(jīng)大于9了, 所以每次對它操作都是在浪費時間

思路2:
排序+兩根指針

這里由于我們還沒有講到排序, 所以對于排序我們直接用js里面提供的sort方法, 如果大家以后面試的話, 除非是考官強制要求不能使用api, 否則能用編程語言提供的api, 我們一定要使用語言自帶的api, 這樣能節(jié)省很多時間

兩根指針的方法在面試中是一個很實用的方法

通過對數(shù)組排序與兩個指針組合, 減少無意義的遍歷
兩根指針: 一根指針(start)指向數(shù)組的第一個元素(數(shù)組中最小元素), 另一個指針(end)指向數(shù)組最后一個元素(數(shù)組中最大元素)
核心思想: 如果現(xiàn)在兩根指針所指元素之和大于目標值, 則表明現(xiàn)在兩數(shù)之和過大, 應使end指針指向更小的數(shù), 即索引減小(end--), 反之則表明現(xiàn)在兩數(shù)之和過小, 應使start指針指向更大的數(shù), 即索引增加(start++)

function sum(arr, target) {
  let start = 0
  let end = arr.length-1
  let result = []
  let index = 0
  if(arr.length < 2) {
    return result
  }
  arr.sort((x,y) => {
    return x-y
  })
  while(start < end) {
    if(arr[start] + arr[end] > target) {
      end--
      continue
    }else if(arr[start] + arr[end] < target) {
      start++
      continue
    }else if(arr[start] + arr[end] === target) {
      result[index] = []
      result[index].push(arr[start])
      result[index].push(arr[end])
      start++
      index++
      continue
    }
  }
  return result
}

思路2總結(jié):

通過對數(shù)組排序與兩根指針組合, 減少無意義的遍歷
使用兩個指針(而不是一個)以相同/相反的方向遍歷數(shù)組
時間復雜度分析: 排序: O(nlogn), 兩根指針算法: O(n)
時間復雜度: O(nlogn) + O(n) => O(nlogn)

例2: 三數(shù)之和

給定一個包含n個整數(shù)的數(shù)組(無重復元素)和一個目標值, 找出數(shù)組中和為目標值的三個數(shù)
例如:
給定一個數(shù)組nums = [-1, 0 ,1, 2, -5, 3], target = 0
滿足要求的三元組集合為:[[-1,0,1], [2,-5,3]]

思路1:

暴力解法
算法復雜度: O(n³)
注意: 面試的時候這種算法基本上不用寫了, 太蠢了, 最多可以當成你思路的第一步告訴面試官
嘗試用排序+兩根指針算法
遍歷第一個數(shù)字num1, 看看另外兩個數(shù)之和是否能滿足target - num1, 這就轉(zhuǎn)化成兩數(shù)之和的問題了
時間復雜度: 排序O(nlogn), 兩數(shù)之和: O(n²)
O(nlogn) + O(n²) => O(n²)

function sum(arr, target) {
  let result = []
  let first
  let second = arr.length - 1
  let index = 0
  if(arr.length < 3) {
    return result
  }
  arr.sort((x,y) => {
    return x-y
  })
  for(let i=0; i<arr.length; i++ ) {
    first = i+1
    while(first < second) {
      if(arr[first] + arr[second] > target - arr[i]) {
        second--
        continue
      }else if(arr[first] + arr[second] < target - arr[i]){
        first++
        continue
      }else if(arr[first] + arr[second] === target - arr[i]) {
        result[index] = []
        result[index].push(arr[i])
        result[index].push(arr[first])
        result[index].push(arr[second])
        first++
        index++
        continue
      }
    }
  }
  return result
}

K-sum解法總結(jié)

排序
嘗試遍歷第一個數(shù), 將問題轉(zhuǎn)化成(K-1)Sum, 以此類推
時間復雜度
2-Sum: O(nlogn) + O(nlogn) => O(nlogn)
3-Sum: O(nlogn) + O(n²) => O(n²)
4--Sum: O(nlogn) + O(³) => O(n³
5-Sum: O(nlogn) + O(n^(k-1)) => O(n^(k-1))

例3: 反轉(zhuǎn)數(shù)組

給定一個數(shù)組, 反轉(zhuǎn)數(shù)組中的所有數(shù)字
例:
Input: {1,2,88,45,3,7}
Output: {7,3,45,88,2,1}

分析:

數(shù)組是否合法
數(shù)組是否已經(jīng)排序
數(shù)組是否有重復元素

這到底就很簡單了

用雙指針, fisrt指向數(shù)組的第一個, end指向數(shù)組的最后一個
交換arr[first]和arr[end]的值.然后指針first++往后移一位, 同時end--往前移一位
直到first >= end(指針first和end相遇, 即表示整個數(shù)組已經(jīng)遍歷完), 結(jié)束交換

function reverse(arr) {
  let first = 0
  let end = arr.length - 1
  
  while(first < end) {
    [arr[first], arr[end]] = [arr[end], arr[first]]
    first++
    end--
  }
  return arr
}

算法復雜度: O(n)

例4: 奇數(shù)偶數(shù)排序

給定一組數(shù)組, 對它們進行排序, 以便所有奇數(shù)整數(shù)在偶數(shù)整數(shù)之前出現(xiàn)。元素順序可以改變编振。排序的奇數(shù)和偶數(shù)的順序無關(guān)緊要肖方。
例:
Input:{4,3,5,2,1,11,0,8,6,9}
Output:{9,3,5,11,1,2,0,8,6,4}

思路:

第一步先用暴力解法:
額外開辟兩個數(shù)組, 一個數(shù)組存儲奇數(shù), 一個數(shù)組存儲偶數(shù), 然后依次先把奇數(shù)輸出, 再把偶數(shù)輸出到另外一個新數(shù)組, 這種解法時間復雜度為O(n), 但是要另外開辟三個新數(shù)組, 所以要浪費額外空間復雜度O(n)
用雙指針
1. 跟之前所有套路一樣, first指向數(shù)組第一個, end指向數(shù)組最后一個
2. 從數(shù)組的第一個開始判斷, 如果是奇數(shù), 則first++,指向數(shù)組的下一個元素,繼續(xù)判斷, 直到遇到偶數(shù),指針first記錄偶數(shù)的位置街望。這時候從數(shù)組的最后一個開始判斷, 如果是偶數(shù), 則end--, 指針指向數(shù)組前一個元素, 繼續(xù)判斷, 直到遇到奇數(shù), end記錄奇數(shù)的位置寺鸥。交換first位置和end位置的兩個數(shù)
3. 交換完成后, 按照第二步的方法繼續(xù)往后判斷, 知道firt指針和end指針相遇(first >= end), 就完成了排序

function swap(arr) {
  let first = 0
  let end = arr.length-1
  while(first < end) {
    while(first < end && arr[first] % 2 === 1) {
      first++
    }
    while(first < end && arr[end] % 2 === 0) {
      end--
    }
    [arr[first],arr[end]] = [arr[end], arr[first]]
    first++
    end--
  }
  return arr
}

總結(jié):

因為這個算法只遍歷了一遍數(shù)組, 所以時間復雜度: O(n)
沒有開辟額外的內(nèi)存空間, 所以空間復雜度: O(1)
相比暴力算法時間復雜度是一樣的, 但是節(jié)省了空間

例5: 合并兩個有序數(shù)組

給定兩個有序整數(shù)數(shù)組, 按照遞增順序?qū)⑺麄兒喜⒌揭粋€排序數(shù)組中
Input: {1,3,5}, {2,4,6}
Output: {1,2,3,4,5,6}

分析:

數(shù)組是否已排序
數(shù)組是否有重復
返回什么數(shù)據(jù)

思路:

同樣用雙指針, 但是這次不太一樣, 這次的雙指針分別指向兩個數(shù)組, 并且指針移動方向相同
開辟一個新數(shù)組保存排序后的數(shù)組, 數(shù)組長度為兩個待排序數(shù)組長度之和
兩個數(shù)組都從第一個開始遍歷，從第一個位置開始比較兩個數(shù)組元素的值, 值比較小的那個元素輸入到新開辟的數(shù)組中的第一個位置, 然后小值所在的數(shù)組索引+1, 大值得數(shù)組索引不變
拿之前小值所在的數(shù)組位置1的元素跟大值數(shù)組位置0的做對比, 跟上面上一樣, 哪個值小, 他所在的數(shù)組索引值就+1, 值大的那個數(shù)組索引不變, 繼續(xù)比直到其中一個數(shù)組所有元素都遍歷完了
當一個數(shù)組所有的值遍歷完, 另一個數(shù)組還沒有遍歷完時, 將沒有遍歷完的數(shù)組剩下的值依次輸入到新數(shù)組中余下的位置
新數(shù)組中的元素就是排序結(jié)果

function merge(arr1, arr2) {
  let mergeArr = new Array(arr1.length + arr2.length)
  let [index,index1,index2] = [0,0,0]
  
  while(index1 < arr1.length && index2 < arr2.length) {
    if(arr1[index1] <= arr2[index2]) {
      mergeArr[index] = arr1[index1]
      index1++
      index++
    }else if(arr1[index1] > arr2[index2]) {
      mergeArr[index] = arr2[index2]
      index2++
      index++
    }
  }
  
  for(let i = index1; i<arr1.length; i++) {
    mergeArr[index] = arr1[i]
    index++
  }
  
  for(let i = index2; i<arr1.length; i++) {
    mergeArr[index] = arr2[i]
    index++
  }
  return mergeArr
}