-1

对包含 2 个已排序子数组的数组进行排序最优化的排序算法是什么？

当我解决这个问题时出现了：https ://leetcode.com/problems/squares-of-a-sorted-array/

我的解决方案如下：

    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        l, r = 0, n-1
        res = [0] * n
        
        for i in range(n-1, -1, -1):
            if abs(nums[l]) > abs(nums[r]):
                res[i] = nums[l] ** 2
                l += 1
            else:
                res[i] = nums[r] ** 2
                r -= 1
        return res

然而，这个解决方案胜过我的：

    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted([i * i for i in nums])

如果 timsort 对小块进行插入排序，那么这样的数组不会在一半的运行中导致 O(n^2) 吗？这比我所谓的 O(n) 解决方案好多少？

谢谢！

4

1 回答 1

2

在这种情况下，理论上的时间复杂度为 O(n)，因为您根本不需要排序（只需合并两个有序列表）。执行排序通常具有 O(NlogN) 复杂度。

然而，复杂性和性能是两件不同的事情。您在 Python 代码中的 O(n) 解决方案正在与高度优化的低级 C 代码中的 O(NlogN) 竞争。理论上，列表的大小应该足够大，以使基于 Python 的 O(n) 解决方案赶上原生排序的 O(NlogN) 配置文件，但您可以预期这将是一个非常大的点元素的数量（可能大于计算机内存可以容纳的数量）。如果 Python 的原生排序足够聪明，可以切换到整数的基数排序算法，或者如果它的排序算法受益于部分排序的数据，那么它就不可能赶上。

于 2021-03-17T12:07:00.380 回答