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

283. 移动零

题目描述 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作,不能拷贝额外的数组。 尽量减少操作次数。 https://leetcode-cn.com/problems/move-zeroes/ 解法1 – 选择排序思想O(n^2) 这道题比较简单,一开始我想的是用选择排序的思想,如果nums[i] == 0,我们就从j = [i+1, |nums|)中找第一个不为0的元素交换到nums[i],然后i++。这种做法是可行的,但是时间复杂度为O(n^2),太蠢了。 解法2 – 双指针O(n) 解法2采用双指针法,首先我们用header指针指向数组第0个元素,然后使用指针i遍历nums数组每个元素,当nums[i] != 0时,我们将nums[i]覆盖到数组头部,即nums[header++] = nums[i]。当i指针遍历到数组末尾,header之前所有的元素都是非0元素,我们将header指向位置之后的所有元素用0填充就是答案。 时间复杂度O(n),空间复杂度O(1)。全部代码如下:

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

327. 区间和的个数

题目描述 给定一个整数数组 nums,返回区间和在 [lower, upper] 之间的个数,包含 lower 和 upper。区间和 S(i, j) 表示在 nums 中,位置从 i 到 j 的元素之和,包含 i 和 j (i ≤ j)。 说明:最直观的算法复杂度是 O(n2) ,请在此基础上优化你的算法。 示例: 输入: nums = [-2,5,-1], lower = -2, upper = 2, 输出: 3 解释: 3个区间分别是: [0,0], [2,2], [0,2],它们表示的和分别为: -2, -1, 2。 https://leetcode-cn.com/problems/count-of-range-sum/ 解法1 先解释下naive的做法,为了计算区间和,一般来说prefix sum是少不了的。有了prefix sum,我们可以在O(1)的时间计算出区间和。首先定义一个数组preSum[i] = sum(nums[0]…nums[i])。然后我们计算符合lower<=preSum[j] – preSum[i]<=upper的次数。显然,这种做法的时间复杂度是O(n^2)。 解法1采用merge sort。我们回忆“315.计算右侧小于当前元素的个数”,我们将题目的目标形式化定义: counts[i] = 统计 nums[i] < nums[j] 成立的次数,0 <= i < j < n 在那道题中,我们将nums进行merge sort,在merge的过程时,用rightCount变量统计nums[i] > nums[j]的次数,当下一次nums[i]…

Read more

315.计算右侧小于当前元素的个数

题目描述 给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。 示例: 输入: [5,2,6,1] 输出: [2,1,1,0] 解释: 5 的右侧有 2 个更小的元素 (2 和 1). 2 的右侧仅有 1 个更小的元素 (1). 6 的右侧有 1 个更小的元素 (1). 1 的右侧有 0 个更小的元素. https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/ 解法1 解法1采用Merge sort。之所以采用Sort是因为第i个数右边小于nums[i]的数字在排序后都会跑到nums[i]的左边,我们只需要在排序的过程中跟踪那些从nums[i]右边跑到nums[i]左边元素的个数,就能够求得答案。 我们举例nums = [5,4,3,1],解释使用Merge sort计算计算过程。 在执行Merge sort过程中,Sort([5, 4, 3, 1])会被拆分为{Sort([5, 4]), Sort([3, 1])},然后Sort([5, 4])又会被拆分为{Sort([5]), Sort([4])}。当发现对独立的元素排序(如Sort([5])),它自然是有序的,将不会执行任何操作直接返回。为了简化图1,我并没有绘制对于单个元素sort的调用过程。 当Sort([5])与Sort([4])返回后,将两个有序的列表[5]与[4]进行Merge。而在Merge的过程中,我们就可以“跟踪”那些从num[i]后面跑到num[i]前面的元素个数,这也正是我们要求的counts[i]。 需要注意,我们对nums直接排序会破坏nums的顺序,而题目要求我们按照nums原有的顺序输出到counts。为了不破坏nums,我们不能对nums排序,而是使用索引数组originIndices记录nums元素对应的索引,我们将nums的索引排序。 排序前nums = [5, 4, 3, 1]originIndices…

Read more

164. 最大间距

题目描述 给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。 如果数组元素个数小于 2,则返回 0。 示例 1: 输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 示例 2: 输入: [10] 输出: 0 解释: 数组元素个数小于 2,因此返回 0。 说明: 你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。 https://leetcode-cn.com/problems/maximum-gap/ 解法1 解法1使用Radix sort(基数排序)。因为题目要求线性的时间复杂度,而所有的基于比较的排序算法平均时间复杂度最优也只有O(nlogn)。而使用基数排序,当数组长度为n,数组中位数最多的数字有w位,那么基数排序的时间复杂度能达到O(wn)。此外,题目提到了数字是非负整数,这样实现Radix sort会更加容易。 题目中说明了数字是能用32位整数表示的,那么2^32 = 2,147,483,647,只有10位。也就是说w=10,是一个常数。那么在题目的限制下,时间复杂度可以认为是O(n),符合题意。而Radix sort是非原地排序,需要长度位n的辅助数组,空间复杂度为O(n),也符合题意。 我们以”nums = [13,23,36,39,11]”为例,来解释Radix的执行过程。首先,我们需要长度为10的数组count,来记录每个数字的个位数出现几次。 nums = [13,23,36,39,11]” 当前位:个位count:idx content0 01 12 03 24 05…

Read more

148. 排序链表

题目描述 在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5 https://leetcode-cn.com/problems/sort-list/ 解法1 – 自顶向下的归并排序 首先,时间复杂度限定O(nlogn),那么在常见的排序算法中,可选的排序算法只有快排、堆排序和归并排序。因为采用了链表这种数据结构,快排和堆排序需要随机访问,因此归并排序较为合适。此外,题目要求常熟级的空间复杂度,也就是说要求原地排序,我们就不能将链表转化为数组排序后再转化为链表。我们在这里贴出常见的排序算法以及相应的空间/时间复杂度。 归并排序分为自顶向下和自底向上两种实现方式,自顶向下需要使用递归来把待排序的数组拆分成两部分,这个过程持续直到待拆分的元素只剩下一个,这一个元素当然是排序好的了。然后我们逐层返回,将排序好的两部分归并,那么归并后的链表也是有序的。严格地说,自顶向下的归并排序并不是常数级空间复杂度,因为递归过程中消耗了系统栈。 下面以示例1: 4->2->1->3为例,图解自顶向下的归并排序过程。为了将链表分为相等的两部分,我们需要寻找链表的中间节点。在这里我们使用了一个技巧,只需要遍历一遍链表就能找到中间节点。 我们寻找到中间节点,记为mid。我们还需要找到中间节点的前一个节点midPrev,因为我们需要将链表断开形成左右两个独立的链表。如果不断开,在寻找中间节点的过程会形成无限递归!!! [4->2->1->3]会被拆分成[4->2], [1->3]两部分,而[4->2]又会被拆分成[4]和[2]两部分。当链表只剩下一个元素时,自然就是排好序的。我们再返回到上一层,将排好序的元素归并。[4]与[2]归并后会形成[2->4]的链表,而[1]与[3]归并会形成[1->3]的链表,我们再返回更上一层将[2->4]与[1->3]归并得到最终结果[1->2->3->4]。全部代码如下所示。

Read more