算法学习(三): 数组

2018-05-28 本文已影响0人 squall1744

数组的基本概念

定义:

通常由一组相同类型的元素的集合所组成的结构(javascript允许数组中包含不同类型的元素)
计算机会分配一块连续的内存来存储这个元素集合
利用索引可以取出元素对应的存储地址

特性:

在内存中为连续空间
定址公式: addr(curElem)=addr(intialElem)+sizeof(curElem)*index
通过index获取数组元素的时间复杂度为O(1)
通常数组第一个位置的索引是0

数组示意图如下:

在java中可以这么定义一个数组

int[] array = {2,4,5,6,22,89,35} //定义数组

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

我们还可以定义二维数组

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

三维数组也是可以定义的, 这里就不举例了

为什么使用数组

简化代码, 提高效率
将相同类型的元素组织在一起

比如, 我们要存1-1000这1000个数, 用数组就能很简单的存储, 并且由于数组的每一个元素都是连续开辟的内存空间, 所以也能快速的取到中间任意的值

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

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

常见数组算法题

因为我自己比较熟悉js, 所以关于算法题的代码, 我都用js代码写, 当然我也只是个初学者, 所以大家不要纠结我代码写的好不好看, 主要看解题思路就好了

例1: 两数之和

给定一个整数数组(无重复元素)和一个目标值, 找出数组中和为目标值的两个数。
按照从小到大的顺序输出结果对
将所有结果对输出到一个数组
例:
Input: number = {2,7,11,15}, target = 9

Output: {2,7}

分析需求:

数组是否排序
有没有重复元素
结果是返回全部还是返回任意一个

解题思路:

思路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总结:

时间复杂度O(n²)
存在无意义操作
例如:
78已经大于9了, 所以每次对它操作都是在浪费时间

思路2:
排序+两根指针

这里由于我们还没有讲到排序, 所以对于排序我们直接用js里面提供的sort方法, 如果大家以后面试的话, 除非是考官强制要求不能使用api, 否则能用编程语言提供的api, 我们一定要使用语言自带的api, 这样能节省很多时间

两根指针的方法在面试中是一个很实用的方法

通过对数组排序与两个指针组合, 减少无意义的遍历
两根指针: 一根指针(start)指向数组的第一个元素(数组中最小元素), 另一个指针(end)指向数组最后一个元素(数组中最大元素)
核心思想: 如果现在两根指针所指元素之和大于目标值, 则表明现在两数之和过大, 应使end指针指向更小的数, 即索引减小(end--), 反之则表明现在两数之和过小, 应使start指针指向更大的数, 即索引增加(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总结:

通过对数组排序与两根指针组合, 减少无意义的遍历
使用两个指针(而不是一个)以相同/相反的方向遍历数组
时间复杂度分析: 排序: O(nlogn), 两根指针算法: O(n)
时间复杂度: O(nlogn) + O(n) => O(nlogn)

例2: 三数之和

给定一个包含n个整数的数组(无重复元素)和一个目标值, 找出数组中和为目标值的三个数
例如:
给定一个数组nums = [-1, 0 ,1, 2, -5, 3], target = 0
满足要求的三元组集合为:[[-1,0,1], [2,-5,3]]

思路1:

暴力解法
算法复杂度: O(n³)
注意: 面试的时候这种算法基本上不用写了, 太蠢了, 最多可以当成你思路的第一步告诉面试官
尝试用排序+两根指针算法
遍历第一个数字num1, 看看另外两个数之和是否能满足target - num1, 这就转化成两数之和的问题了
时间复杂度: 排序O(nlogn), 两数之和: 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解法总结

排序
尝试遍历第一个数, 将问题转化成(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: 反转数组

给定一个数组, 反转数组中的所有数字
例:
Input: {1,2,88,45,3,7}
Output: {7,3,45,88,2,1}

分析:

数组是否合法
数组是否已经排序
数组是否有重复元素

这到底就很简单了

用双指针, fisrt指向数组的第一个, end指向数组的最后一个
交换arr[first]和arr[end]的值.然后指针first++往后移一位, 同时end--往前移一位
直到first >= end(指针first和end相遇, 即表示整个数组已经遍历完), 结束交换

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: 奇数偶数排序

给定一组数组, 对它们进行排序, 以便所有奇数整数在偶数整数之前出现。元素顺序可以改变。排序的奇数和偶数的顺序无关紧要。
例:
Input:{4,3,5,2,1,11,0,8,6,9}
Output:{9,3,5,11,1,2,0,8,6,4}

思路:

第一步先用暴力解法:
额外开辟两个数组, 一个数组存储奇数, 一个数组存储偶数, 然后依次先把奇数输出, 再把偶数输出到另外一个新数组, 这种解法时间复杂度为O(n), 但是要另外开辟三个新数组, 所以要浪费额外空间复杂度O(n)
用双指针
1. 跟之前所有套路一样, first指向数组第一个, end指向数组最后一个
2. 从数组的第一个开始判断, 如果是奇数, 则first++,指向数组的下一个元素,继续判断, 直到遇到偶数,指针first记录偶数的位置。这时候从数组的最后一个开始判断, 如果是偶数, 则end--, 指针指向数组前一个元素, 继续判断, 直到遇到奇数, end记录奇数的位置。交换first位置和end位置的两个数
3. 交换完成后, 按照第二步的方法继续往后判断, 知道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
}

总结:

因为这个算法只遍历了一遍数组, 所以时间复杂度: O(n)
没有开辟额外的内存空间, 所以空间复杂度: O(1)
相比暴力算法时间复杂度是一样的, 但是节省了空间

例5: 合并两个有序数组

给定两个有序整数数组, 按照递增顺序将他们合并到一个排序数组中
Input: {1,3,5}, {2,4,6}
Output: {1,2,3,4,5,6}

分析:

数组是否已排序
数组是否有重复
返回什么数据

思路:

同样用双指针, 但是这次不太一样, 这次的双指针分别指向两个数组, 并且指针移动方向相同
开辟一个新数组保存排序后的数组, 数组长度为两个待排序数组长度之和
两个数组都从第一个开始遍历，从第一个位置开始比较两个数组元素的值, 值比较小的那个元素输入到新开辟的数组中的第一个位置, 然后小值所在的数组索引+1, 大值得数组索引不变
拿之前小值所在的数组位置1的元素跟大值数组位置0的做对比, 跟上面上一样, 哪个值小, 他所在的数组索引值就+1, 值大的那个数组索引不变, 继续比直到其中一个数组所有元素都遍历完了
当一个数组所有的值遍历完, 另一个数组还没有遍历完时, 将没有遍历完的数组剩下的值依次输入到新数组中余下的位置
新数组中的元素就是排序结果

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
}

总结:

时间复杂度: 因为分别需要遍历两个数组, 所以为O(m+n)
空间复杂度: 开辟了新的数组用来保存排序后的结果, 所以额外空间复杂度为O(m+n),
这个空间是必须开辟的, 所以这并不算浪费空间

关于数组我们就说到这里, 请大家期待下次的更新吧.