1. 最小的k个数

题目:输入n个整数,找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

1.1思路一:堆排

如果维护k个大小的数组:

1. 当输入的数小于等于k个时，直接放入数组中,
2. 当输入的数大于k个时，拿输入数与k个数中最大的数比较;如果输入数小于k中的最大数,则替换输入数到k个数中;否则忽略。
3. 维护这样的k个数，可以使用大顶堆。
   细节:注意k的数可能大于数组个数，可能小于1个
   堆排的空间复杂度是o(1),时间复杂度是nlog(k)

源码

func minKArr(arr:[Int],k:Int) -> [Int] {
        if k<1 || k>arr.count {
            return []
        }
        var arr = arr
        //构建大顶堆
        for i in (0...k/2).reversed() {
            heapAdjust(arr: &arr, parent: i, len: k)
        }

        for i in k..<arr.count {
            if arr[i]<arr[0] {//有新的数时，不断调整大顶堆
                arr[0] = arr[i]
                heapAdjust(arr: &arr,parent: 0,len: k)
            }
        }
        return Array(arr[0..<k])
    }
    
    func heapAdjust(arr:inout [Int],parent:Int,len:Int) {
        let temp = arr[parent]
        
        var parent = parent
        var child = 2*parent+1
        while child<len {
            if child+1<len && arr[child]<arr[child+1] {
                child += 1
            }
            
            if temp<arr[child] {
                arr[parent] = arr[child]
                parent = child
                child = 2*child+1
            }else{
                break
            }
        }
        arr[parent] = temp
    }

1.2思路二:快排

快排的思路:
最小的k个数，即下标位于k-1的位置
选中的数index如果刚好是k-1，则k-1及左边的数都是数组中最小的k个数
选中的数index如果在k-1的左边,则需要在index+1的右边去查找
选中的数index如果在k-1的右边,则需要在index-1的左边去查找

1. 快排选中一个基数,把大的放在基数右边，小的放在基数左边。并返回基数的下标index

func quickSort(arr:inout [Int],start:Int,end:Int) -> Int {
        if start >= end {
            return start
        }
        let key = arr[start]
        var start = start
        var end = end
        
        while start<end {
            while start<end && key<=arr[end] {
                end -= 1
            }
            if start<end {
                arr[start] = arr[end]
            }
            
            while start<end && key>=arr[start] {
                start += 1
            }
            if start<end {
                arr[end] = arr[start]
            }
            
        }
        arr[start] = key
        return start
    }

2. 按查找的index与k-1的位置进行递归查找

func minKArr2(arr:[Int],k:Int) -> [Int] {
        if k>arr.count || k<=0 {
            return []
        }
        var arr = arr
        
        var start = 0
        var end = arr.count-1
        var index = quickSort(arr: &arr, start: start, end: end)
        while index != k-1 {
            if index>k-1 {
                end = index-1
            }else{
                start = index+1
            }
            index = quickSort(arr: &arr, start: start, end: end)
        }
        return Array(arr[0..<k])
    }

2. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
简单的思路:遍历数组肯定能得到结果，但肯定不是最好的
进阶:出现一般的数，如果存在这样的数，则一定是数组的中位数
利用快排来选取这个中位数,第一题思路二利用快排找出第k个数的位置,把k=n/2就是本题的答案。

2.1 思路:快排

func moreHalfArrNum(arr:inout [Int]) -> Int {
        if arr.count <= 1 {
            return arr.first ?? 0
        }
        var index = quickSort(arr: &arr, start: 0, end: arr.count-1)
        let middle = arr.count >> 1
        var start = 0
        var end = arr.count-1
        
        while index != middle {
            if index > middle {
                end = index-1
            }else{
                start = index+1
            }
            index = quickSort(arr: &arr, start: start, end: end)
        }  
        return arr[middle]
    }

如果要考虑没有这样的数，可做个校验检查。本题还有其他思路，读者可参考《剑指offer》。

3.数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

3.1 思路:归并

如果理解归并排序，这道题非常好理解。在合并的时候,如果出现arr[l]>arr[r]的时候，则统计数。

3.2 源码

func reverseOrder(arr:inout [Int]) -> Int {
        if arr.count < 2 {
            return 0
        }
        var count = 0
        var tmp = Array.init(repeating: 0, count: arr.count)
        mergeArr(arr: &arr, left: 0, right: arr.count-1, tmp: &tmp,count: &count)
        return count
    }
    
    func mergeArr(arr:inout [Int],left:Int,right:Int,tmp:inout [Int],count:inout Int) {
        if left>=right {
            return
        }
        let mid = (left+right)/2
        mergeArr(arr: &arr, left: left, right: mid, tmp: &tmp,count: &count)
        mergeArr(arr: &arr, left: mid+1, right: right, tmp: &tmp,count: &count)
        
        mergeTwoArr(arr: &arr, left: left, mid: mid, right: right, tmp: &tmp,count: &count)
    }
    
    
    func mergeTwoArr(arr:inout [Int],left:Int,mid:Int,right:Int,tmp:inout [Int],count:inout Int) {
        var k = 0
        
        var l = left,r = mid+1
        while l<=mid && r<=right {
            if arr[l]<=arr[r] {
                tmp[k] = arr[l]
                l += 1
            }else{
                tmp[k] = arr[r]
                r += 1
                count += (mid - l + 1) ////如果l>r证明l到mid数都大于r的数
            }
            k += 1
        }
        
        while l<=mid {
            tmp[k] = arr[l]
            l += 1
            k += 1
        }
        
        while r<=right {
            tmp[k] = arr[r]
            r += 1
            k += 1
        }
        
        k = 0
        for i in left...right {
            arr[i] = tmp[k]
            k += 1
        }

    }

题中需要理解的是count += (mid - l + 1)。如果l>r证明l到mid数都大于r的数

总结:

1. 题中的解法并非所有都是最优解，但能够对排序有更好的理解。以上题目来自《剑指offer》。
2. 每种解法都经过leetcode验证通过。