数组算法

 

一些算法举例

数组

二分插入法

给出一个有序数组(入从小到大),将指定的数字插入合适的位置,返回index。

  • 示例
输入:[1, 2, 3, 4, 6, 7, 8, 9, 10, 10, 11, 18, 76],14
输出:11
  • 思路

上下边界,二分判断,直到下边界>=上边界,退出循环

  • 解法
func binarySearch(insert target: Int, into src: [Int]) -> Int {
    var left=0, right=src.count-1
    
    while left<=right {
        let mid=(left+right)/2
        let midValue=src[mid]
        
        if target==midValue {
            return mid
        } else if target>midValue {
            left=mid+1
        } else {
            right=mid-1
        }
    }
    
    print("\(target) Should insert at Index: \(left)")
    return left;
}
  • 测试

let _=binarySearch(insert: 14, into: source)

14 Should insert at Index: 11

寻找中间数

给出一个无序数组,求出一个数,使得其左边的数都小于它,右边的数都大于等于它。要求时间复杂度为n

  • 示例
输入:[4,3,2,7,9,10,11,10]
输出:7,9
  • 思路

两次遍历,第一次遍历,记录下每个位置和它之后的那个元素的最小值(当然这个最小值会一直更新,所以这一次遍历完,就是整个数组的最小值),需要一个n的数组,存放的是这个位置和它后面一个位置的较小值,当然如果已经遇到了,最小值,因为会和最小值进行判断,所以后续这个新的数组里存放的都是这个最小值了。

第二次遍历是正常的从左向右遍历,寻找左边大且比右边小的数,也会记住一个最大值。

  • 解法
func findTheMidNumber(_ data: [Int]) -> [Int] {
  var res = [Int]()

  if data.count == 0 {return res}
  if data.count <= 2 {return res}

  var rightMin = [Int](repeating: 0, count: data.count)
  var r_min = data[data.count-1]

  //从右往左,寻找每个位置及其之后的最小数
  for i in (0..<data.count).reversed() {
    if data[i] < r_min {
      r_min = data[i]
    }
    rightMin[i] = r_min
  }

  //从左往右,寻找左边大且比右边小的数
  var l_max = data[0]
  for i in 0..<data.count-1 {
    if data[i] > l_max {
      l_max = data[i]
      if data[i] < rightMin[i+1] {
        res.append(data[i])
      }
    }
  }
  print(res)
  return res
}
  • 测试

_ = findTheMidNumber([4,3,2,7,9,10,11,10])

[7, 9]

三数之和

一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a+b+c=0?请找出所有满足条件且不重复的三元组

注意:不可以包含重复的三元组

  • 示例
输入:nums=[-1,0,1,2,-1,-4]
输出:[[-1,0,1], [-1,-1,2]]
  • 思路

除非三个数全是0,否则肯定会有正数和负数,所以假定选择一个数,然后再去找另外两个数,这样只要找到两个数且和为第一个选择的数的相反数。

  1. 从小到大排序
  2. 循环
  3. 如果最小的数大于0,直接结束(因为必须要有负数)

sort_algorithm

相当于两数之和问题:a+b=target,因为是排好序的,选定了i,那么j+k需要是i的相反数,如果j+k<target,则j++,否则k–,j和k是右边数组的首末两端

  • 解法
func threeSum(_ nums: [Int])->[[Int]]? {
  var tempNums = nums

  if nums.count <= 0 {return nil}
  //排序
  insertSort(arr: &tempNums)
  if tempNums[0] > 0 {return nil}

  var res = [[Int]]()

  for i in 0..<tempNums.count {
    let target = -tempNums[i]

    var j = i+1
    var k = tempNums.count-1

    while k-j > 0 {
      let numj = tempNums[j]
      let numk = tempNums[k]

      if numj+numk < target {
        j += 1
      } else if numj+numk > target {
        k -= 1
      } else {
        //找到,返回i,j,k
        res.append([tempNums[i],numj,numk])
        break
      }
    }
  }

  return res
}
  • 测试
let res = solution.threeSum([-1,0,1,2,-1,-4])
  • 结果

[[-1, -1, 2], [-1, 0, 1]]

岛屿最大面积

给定一个包含了一些 01 的非空二维数组 grid

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)

  • 示例
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

  • 解法
func dfs(_ i: Int,_ j: Int,_ m: Int,_ n:Int,_ grid: inout [[Int]],_ tempArea: inout Int) -> Int {
  if i<0 || i>=m || j<0 || j>=n || grid[i][j] == 0 {
    return tempArea
  }
  grid[i][j] = 0
  tempArea += 1
  tempArea = dfs(i+1, j, m, n, &grid, &tempArea)
  tempArea = dfs(i-1, j, m, n, &grid, &tempArea)
  tempArea = dfs(i, j+1, m, n, &grid, &tempArea)
  tempArea = dfs(i, j-1, m, n, &grid, &tempArea)
  return tempArea
}

func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
  var tempGrid = grid
  var area = 0
  let m = tempGrid.count
  var n = 0
  var islandMax = 0
  for i in 0..<m {
    n = tempGrid[i].count
    for j in 0..<n {
      area = 0
      area = dfs(i, j, m, n, &tempGrid, &area)
      islandMax = max(islandMax, area)
    }
  }
  return islandMax
}

最长递增子序列(非连续)

给定一个未经排序的整数数组,找到最长递增子序列

  • 示例
输入:10,9,2,5,3,7,101,18,20
输出:2,3,7,18,20
  • 思路

    • 动态规划的方式: 第一层循环省不了:for i:0->n-1。
      • 状态定义:DP[i]表示从头到第i个元素,且第i个元素要被选上的最长子序列的长度。DP[i]不是最后一个的长度,实际上是max{DP[0],DP[1]…DP[i-1]}+1,因为i必须要被选上。
      • 状态转移方程:for i:0->n-1 {for j:0->i-1} 两层循环,时间复杂度是O(\(n^2\))

    DP[i]=max{DP[j]}+1, j:0->i-1 且a[j]<a[i]

    • 一个巧妙的方法: 上述方式,只能第二层循环才能加速。一般来说第一遍for i->n-1(n),第二遍for j->i-1(n).这里可以加速的是第二个循环,因为第一个循环肯定是不能加速的,所以只能加速第二个循环。可以维护一个数组LIS(最后的结果数组),一开始数组是空的,当第一个数10进来,毫无疑问,它就是最长递增子序列,9进来的时候,如果它比10大则直接append,否则用二分查找法去找到数组中比它大的最小的数,替换掉,因为我们相当于要不断让更小的数进来,所以很好理解。这个复杂度是logn的,所以整体是nlogn的时间复杂度。
  1. DP方式:
    • 实现
         //寻找最长上升子序列(不需要连续),10,9,2,5,3,7,101,18,20->2,3,7,18,20
         func findLongestIncrementSequenceWithDP(src: [Int]) -> Int {
             if src.count<=0 {
                 return 0
             }
                  
             var rls=1
                  
             var DP = Array.init(repeating: 1, count: src.count)
                  
             for i in 1..<src.count {
                 for j in 0..<i {
                     if src[j]<src[i] {
                         DP[i]=max(DP[i], DP[j]+1)
                     }
                 }
                      
                 rls=max(rls, DP[i])
             }
                  
             print("\(src)'s LIS count is \(rls)")
             return rls
         }
      
    • 结果

      let _=findLongestIncrementSequenceWithDP(src: [10,9,2,5,3,7,101,18,20])

      [10, 9, 2, 5, 3, 7, 101, 18, 20]’s LIS count is 5

  2. 巧妙方式
    • 实现

       //寻找最长上升子序列(不需要连续),10,9,2,5,3,7,101,18,20->2,3,7,18,20
       func findLongestIncrementSequence(src: [Int]) -> [Int] {
           if src.count<=0 {
               return []
           }
                
           var rls=[Int]()
                
           for i in 0..<src.count {
               let index=binarySearch(insert: src[i], into: rls)
                    
               rls.insert(src[i], at: index)
                    
               if index+1<rls.count {
                   rls.remove(at: index+1)
               }
           }
                
           print("\(src)'s LIS is \(rls)")
           return rls
       }
      

      其中binarySearch是笔者自己实现的二分查找,找到应该插入的位置,所以后续还要删除原来的数字,等于是替换。如果标准库有对应的low_bounder方法,则不需要自己实现。

    • 结果

      let _=findLongestIncrementSequence(src: [10,9,2,5,3,7,101,18,20])

      [10, 9, 2, 5, 3, 7, 101, 18, 20]’s LIS is [2, 3, 7, 18, 20]

最长连续递增序列

给定一个未经排序的整数数组,找到最长且连续的递增序列,并返回该序列的长度。

  • 示例
输入:[1,3,5,4,7]
输出:3
解释:最长递增序列是[1,3,5], 长度为3

输入:[2,2,2,2]
输出:1
解释:最长连续递增序列是[2], 长度为1

:数组长度不超过10000

  • 思路
    • count 为当前元素峰值,ans为最大峰值
    • 初始化 count=1
    • 从0位置开始遍历,遍历是根据前后元素状态判断是否递增,递增则count++,递减count=1
    • 如果count>ans,则更新ans
    • 直到循环结束
  • 解法
func findLengthOfLCIS(_ nums: [Int])->Int {
  if nums.count <= 1 {return nums.count}
  var ans = 1
  var count = 1

  for i in 0..<nums.count-1 {
    if nums[i+1] > nums[i] {
      count += 1
    } else {
      count = 1
    }

    ans = count>ans ? count : ans
  }

  return ans
}
  • 结果

print(solution.findLengthOfLCIS([1,3,5,4,7]))

3

数组中的第K大的元素

在未排序的数组中找到第k大的元素。

  • 示例
输入: [3,2,1,5,6,4], k=2
输出:5

输入: [3,2,3,1,2,4,5,5,6], k=4
输出:4

假设k总是有效的,且1<=k<=数组长度

  • 思路

改进快速排序算法,求得第k大的元素,不需要将快速排序完全进行完,只需要进行一遍的递归,如果q刚好是第k大,则打完收工。

  • 解法
//寻找pivot的函数
func partition(arr: inout [Int], left: Int, right: Int) -> Int {
  let pivot = left
  var index = pivot+1
  for i in index...right {
    if arr[i] < arr[pivot] {
      arr.swapAt(i, index)
      index+=1
      //i和index都更新,以pivot为分隔,两边都冒泡,后面再将假设的pivot替换为真正的pivot,然后继续递归
    }
  }
  //此处相当于pivot需要更新
  arr.swapAt(pivot, index-1)
  return index-1
}

func findKthLargest(_ nums: inout [Int], _ k: Int) -> Int {
  return quickSelect(&nums, 0, nums.count-1, nums.count-k)
}

func quickSelect(_ a: inout [Int], _ l: Int, _ r: Int, _ index: Int) -> Int {
  let q = partition(arr: &a, left: l, right: r)
  if q == index {
    return a[q]
  } else {
    return q<index ? quickSelect(&a, q+1, r, index) : quickSelect(&a, l, q-1, index)
  }
}
  • 结果

var nums = [3,2,3,1,2,4,5,5,6]

let r10 = solution.findKthLargest(&nums, 4)

4

最长连续增序列

给定一个未排序的整数数组,找出最长连续增序列的长度。

要求算法复杂度O(n)

  • 示例
输入:[100,4,200,1,3,2]
输出:4
解释:最长连续序列是[1,2,3,4]。长度为4
  • 思路

使用hashmap来保存数组中已经遍历过的元素,key对应元素的值,value表示该元素所在的连续子数组的长度。如果hash中存在此元素,则遍历下一个元素。如果不存在,则看hashmap中是否存在在此元素的前一个元素,比如如果遍历到5时,看看hash中是否存在4,如果存在则取该连续子数组的子一个元素,将它value值+1,并将该元素放到hashmap中,value值与第一个元素值相同,都表示该连续子数组的长度。如果hashmap中存在的该元素遍历到5时,hashmap中是否存在6,将次元素加入到最后一个连续的子数组中,并且和2中一样,找到子数组的第一个和最后一个元素,将它们的value值更新为子数组的长度。

swift解法简单,先排好序,然后判断i-1的值+1是否等于i的值,是的话,则继续向后,否则,当前和记录的最大值比较,currentstreak=1初始化

  • 解法
func longestConsecutive(_ nums: [Int]) -> Int {
  guard nums.count > 0 else { return 0 }
  let nums = nums.sorted(){$0 < $1}
  
  var longestStreak = 1
  var currentStreak = 1
  for i in 1..<nums.count {
    if nums[i] != nums[i - 1] {
      if nums[i - 1] + 1 == nums[i] {
        currentStreak += 1
      } else {
        longestStreak = max(longestStreak, currentStreak)
        currentStreak = 1
      }
    }
  }
  return max(longestStreak, currentStreak)
}

按频率对整数数组进行排序

应该按频率对数组排序,如果相同的频率则对整数排序

  • 示例
输入:1 1 1 1 1 2 1 2 3 3 3 3 3
输出:1 1 1 1 1 1 3 3 3 3 3 2 2
  • 思路

用hashmap存放数字出现的次数,然后对hashmap的value进行排序

代码实现:

func sortFrequencyArray(source: [Int]) -> [Int] {
  if source.count <= 1 {
    return source
  }

  //key是数字,value是出现的频率
  var hashTable: Dictionary<Int, Int> = [Int:Int]()
  for i in 0..<source.count {
    let key: Int = source[i]

    if hashTable.keys.contains(key) {
      //更新数值
      var value = hashTable[key]
      value! += 1
      hashTable[key] = value
    } else {
      hashTable[key] = 1
    }
  }

  let values = hashTable.sorted{
    if $0.1 == $1.1 {
      //如果value(频率)相等,则按照key倒序
      return $0.0 > $1.0
    }

    //如果value(频率)不等,则按照value倒序
    return $0.1 > $1.1
  }

  var result: [Int] = [Int]()

  for i in 0..<values.count {
    for _ in 0..<values[i].1 {
      result.append(values[i].0)
    }
  }

  return result
}
  • 测试
let array6 = [8,8,8,8,8,8,8,8,8,8,8,8,8,7,7,1,1,6,6,1,1,1,2,1,2,4,4,3,3,5,5]
let array7 = solution.sortFrequencyArray(source: array6)
print(array7)
  • 结果

[8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 7, 7, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2]