Swift Leetcode 数组排序算法题解

1. 合并两个有序数组

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        //思路是使用双指针的思路，这里用到了归并排序的思想
                var i1 = m - 1
                var i2 = n - 1
                var cur = nums1.count - 1
                while i2 >= 0 { //这里必须要大于等于0 代表还没有合并结束
                    if i1 >= 0 && nums2[i2] < nums1[i1] {
                        nums1[cur] = nums1[i1]
                        i1 -= 1
                    }else{ // i1 < 0 || nums2[i2] >= nums1[i1]  这里i1已经为0了
                        nums1[cur] = nums2[i2]
                        i2 -= 1
                    }
                    cur -= 1
                }
    }

解题思路：

双指针法，从后面插入替换合并，把nums2数值添加到nums1，如果在前面插入会替换到后面的数字

只要nums2的指针索引>=0代表还没有合并结束，只要成功合并一次，两个指针索引都需要向后移动一位

这里还需要考虑到比如nums1的长度比nums2 数组长度短的情况，所以 else 里就是 // i1 < 0 || nums2[i2] >= nums1[i1] 这里i1已经为0了这里直接把nums2的数字往nums1数组合并

这里解题思路用到了归并排序算法：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

2. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

1 2	输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

/*
	 * 一个只包含0、1、2的整型数组，要求对它进行【原地】排序
	 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
	 * 
	 * 空间复杂度O(1)，时间复杂度O(n)
	 */
   func sortColors(_ nums: inout [Int]) {
            var i = 0  //当前索引
            var left = 0 //第一个指针
            var right = nums.count - 1 //第二个指针
            while i <= right { // 只有 当 i > right 时，遍历结束
                var v = nums[i]
                if v == 0 {
                   swap(&nums,i,left)
                   i+=1
                   left+=1
                } else if v == 1 {
                   i+=1
                } else {
                   swap(&nums,i,right)
                   right-=1
                }
            }
    }


    func swap(_ nums: inout [Int],_ i:Int ,_ j:Int){
         var tmp = nums[i]
       	 nums[i] = nums[j]
      	 nums[j] = tmp
    }

解题思路：

遇到 1，跳过, i++
遇到 0，跟左指针 left 交换值，并且 left++, i++
遇到 2，跟右指针 right 交换值, right–，重新判断当前 i 的新值。

只有当 i > right 时，遍历结束。

过程有点像快速排序，而且是选择数值为 1 作为锚点。

left 右边代表的是 0 区间， left 本身代表的是 0 这个区间的末尾。

right 的右边才是排好的2的区间，而 right 本身元素远并不确定

所以终止条件是 i <= right

3. 部分排序

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例：
输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]

提示：
0 <= len(array) <= 1000000

func subSort(_ array: [Int]) -> [Int] {

        if array.count == 0 { 
            return [-1, -1] 
        }

        // 从左扫描到右寻找逆序对（正序：逐渐变大）
        var max = array[0]
        // 用来记录最右的那个逆序对位置
        var r = -1
        //先左到右找最大值
        for  i in 1..<array.count {
            let v = array[i]
            if v >= max {
                max = v
            }else{
                r = i
            }
            
        }
        
        // 提前结束
        if r == -1 {
            return [-1,-1]
        }

        // 从右扫描到左寻找逆序对（正序：逐渐变小）
    	var min = array[array.count - 1]
    	// 用来记录最左的那个逆序对位置
        var l = -1
        //先右到左找最小值
        for  i in (0...array.count - 2).reversed() { // swift的倒序遍历
            let v = array[i]
            if v <= min {
                min = v
            }else{
                l = i
            }
                
        }

            return [l,r]

    }

解题思路：

4. 有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

请你设计时间复杂度为 O(n) 的算法解决本问题

func sortedSquares(_ nums: [Int]) -> [Int] {
        var newArray = [Int](repeating: 0, count: nums.count)
        var left = 0
        var right = nums.count-1
        var lastIndex = right //插入的索引位置，从后面插入数组
        while left <= right { //这里一定会执行nums.count次
            let leftNum = nums[left] * nums[left]
            let rightNum = nums[right] * nums[right]
            if leftNum > rightNum {
                newArray[lastIndex] = leftNum
                left+=1 //左指针向右移动
            } else {
                newArray[lastIndex] = rightNum
                right-=1 //右指针向左移动
            }
            lastIndex-=1
        }
        return newArray
    
    }

解题思路：

双指针

因为本身数组就是非递减顺序，所以越靠中间，数值是越靠近的，也是越小的，负负得正，结果都会是正数，所以只要左右边比较即可。每次比较都互相移动一次，即可出结果。

新建一个新的数组，用两个指针，left指针指向第一位，right指针指向最后一位，再申明一个插入索引变量lastIndex，当left指针比right指针大的时候结束遍历，每次遍历判断left边和right边的平方哪个大，如果left边大，那left边插入新数组的最后一个位，left指针向右移动，right指针一样。