324. 摆动排序 II

题目描述 给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。 示例 1: 输入: nums = [1, 5, 1, 1, 6, 4] 输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6] 示例 2: 输入: nums = [1, 3, 2, 2, 3, 1] 输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2] 说明:你可以假设所有输入都会得到有效的结果。 进阶:你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗? https://leetcode-cn.com/problems/wiggle-sort-ii/ 解法1 –…

Read more

215. 数组中的第K个最大元素

题目描述 在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明: 你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ 解法1 – 排序O(nlogn) 这是一道经典的题目,有多种解法。最直接的想法,我们可以先排序,然后取出第n – k个数字。时间复杂度O(nlogn),空间复杂度O(1)。全部代码如下: 运行时间:7ms 解法2 – 堆(优先队列)O(nlogk) 我们维护一个大小为k的最小堆,这可以通过Java的PriorityQueue的默认构造方法构建。我们不断的往堆中加入元素,直到元素数量超过k,我们删除最小元素。当扫描完整个nums数组,堆中就留下了k个最大的数,我们取k个最大数中最小的那一个就是答案。 例如nums = {3,2,1,5,6,4}, k = 2。当堆内容为{3, 2}时,再加入1得到{3, 2, 1},元素数量超过了k,我们删除最小元素1得到{3,…

Read more

75. 颜色分类

题目描述 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意:不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶: 一个直观的解决方案是使用计数排序的两趟扫描算法。首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗? https://leetcode-cn.com/problems/sort-colors/ 解法1 – 桶排序 – O(n) 就像题目描述的直观方法那样,我们声明一个长度为3的数组,下标为0,1,2的位置分别记录0、1、2数字出现的次数。第一次扫描填充桶,第二遍扫描从桶里取数,回填到数组中。 时间复杂度O(n),准确的说是O(2*n);空间复杂度O(1)。全部代码如下: 解法2 – Partition函数 – O(n) 记得快速排序的Partition函数吗?找一个pivot,两个指针指向数组两端,调用partition函数使得左边的元素都小于pivot;右边的元素都大于pivot。这里我们借用Partition函数的思想,用3个指针i、j、k。使得[0, i)的元素都是0、(j, |nums|)的元素都是2,而指针k扫描[0, |nums|)。 当k指向的当前元素是0,就把它与i所指的位置交换,然后i++;当k指向的当前元素是2,就把它与j所指的位置交换,然后j–;如果k指向的元素是1,那就k++。需要注意的是边界问题,k需要满足0<=i <=k <=j<|nums|。下面的条件k>=i实际上是限制i,如果我们不限制,就会使得i超越k,导致越界;对于变量j也是同理。 时间复杂度O(n),空间复杂度O(1)。全部代码如下:

Read more