LeetCode 977. Squares of a Sorte

问题描述

给定一个升序排列的整形数组，要求返回每个元素计算平方值之后的数组，且升序排列。

• 栗子 1：

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

• 栗子 2：

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

注意：

1. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. A 升序排列

想看英文的戳这里：原题地址

解题思路

大脑中最直观闪现的解法

相信大家最先想到的方法，就是分别计算出每个元素的平方值后，然后进行排序，解题完毕，然后大笑一声 哈哈哈，这题这么简单。

swift 代码提交，发现速度并不快，faster than 60%。

func sortedSquares(_ A: [Int]) -> [Int] {
    var squares = [Int]()
    for n in A {
        squares.append(n * n)
    }
    
    // 排序
    return squares.sorted()
}    

暗藏玄机

第一种解法，其实并没有用到题目中给的条件，A 是升序排列的。

下面我们来简单分析一下。

假设 A = [0, 3, 10]，全为正数，那么按原顺序就好；

假设A = [-4, -3, -2]，全为负数，负数越小，平方和越大，那么倒序遍历，刚好是升序的；

假设A = [-4, -3, -2, 0, 3, 10]，既有负数，也有正数，并且负数是有序的，正数也是有序的，于是可以想到将两个有序数组合并成一个有序的数组。

负数数组：[-4, -3, -2]，从后往前遍历，使用其绝对值进行比较。
正数数组：[0, 3, 10]，从前往后遍历。

完整代码如下：

func sortedSquares_2(_ A: [Int]) -> [Int] {
    // 因为 A 已经排好序，找到前面的负数部分从后遍历，和后面的正数部分从前遍历，进行合并
    var negArray = [Int]()
    var result = [Int]()
    
    var i = 0
    // 负数数组
    while i < A.count {
        if A[i] < 0 {
            negArray.append(A[i])
            i += 1
        } else {
            break
        }
    }
    
    var j = negArray.count - 1
    while j >= 0, i < A.count {
        if abs(negArray[j]) < A[i] {
            // 加入数组
            result.append(negArray[j] * negArray[j])
            j -= 1
        } else {
            result.append(A[i] * A[i])
            i += 1
        }
    }
    
    while j >= 0 {
        result.append(negArray[j] * negArray[j])
        j -= 1
    }
    
    while i < A.count {
        result.append(A[i] * A[i])
        i += 1
    }
    
    return result
}

完整代码 Git 地址 ~~ 戳戳戳