Press "Enter" to skip to content

Posts tagged as “sort”

花花酱 LeetCode 3517. Smallest Palindromic Rearrangement I

By zxi on April 16, 2025

这题考查的是排序吧… 还有rbegin的使用。

普通排序：时间 O(nlogn) / 空间 O(1)

前半部分顺序排序，后半部分逆序排序。

计数排序：时间：O(n)，空间：O(n) -> O(1)

首尾一起写

花花酱 LeetCode 368. Largest Divisible Subset

By zxi on April 4, 2025

也算是一道比较经典的DP题了，需要找到一个最大的子集，使得其中元素两两的余数为0。

我们假设有一个集合为{a1, a2, a3, …, an}, {a1 < a2 < … < an)

如果 a2 % a1 = 0, a3 % a2 == 0, 那么a3 % a1 一定也等于0。也就是说a2是a1的倍数，a3是a2的倍数，那么a3一定也是a1的倍数。所以我们并不需要测试任意两个元素之间的余数为0，我们只需要检测a[i]是否为a[i-1]的倍数即可，如果成立，则可以确保a[i]也是a[i-2], a[i-3], … a[1]的倍数。这样就可以大大降低问题的复杂度。

接下来就需要dp就发挥威力了。我们将原数组排序，用dp[i]来表示以a[i]结尾（集合中的最大值），能够构建的子集的最大长度。

转移方程：dp[j] = max(dp[j], dp[i] + 1) if nums[j] % nums[i] = 0.

这表示，如果nums[j] 是 nums[i]的倍数，那么我们可以把nums[j]加入以nums[i]结尾的最大子集中，构建一个新的最大子集，长度+1。当然对于j，可能有好多个满足条件的i，我们需要找一个最大的。

举个例子：
nums = {2, 3, 4, 12}
以3结尾的最大子集{3}，长度为1。由于12%3==0，那么我们可以把12追加到{3} 中，构成{3,12}。
以4结尾的最大子集是{2,4}，长度为2。由于12%4==0，那么我们可以把12追加到{2,4} 中，构成{2,4,12} 。得到最优解。

这样我们只需要双重循环，枚举i，再枚举j (0 <= i < j)。时间复杂度：O(n^2)。空间复杂度：O(n)。

最后需要输出一个最大子集，如果不记录递推过程，则需要稍微判断一下。

花花酱 LeetCode 3462. Maximum Sum With at Most K Elements

By zxi on March 27, 2025

本题使用了两次 partial sorting / std::nth_element 来进行部分排序，可以作为经典教程了。

速度比全排序或者heap/pq快到不知道哪里去了～

Time complexity: O(m*n)
Space complexity: O(m*n)

不用黑科技就达到99.77%

花花酱 LeetCode 2441. Largest Positive Integer That Exists With Its Negative

By zxi on October 15, 2022

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

Constraints:

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

Solution 1: Hashtable

We can do in one pass by checking whether -x in the hashtable and update ans with abs(x) if so.

Time complexity: O(n)
Space complexity: O(n)

C++

Solution 2: Sorting

Sort the array by abs(x) in descending order.

[-1,10,6,7,-7,1] becomes = [-1, 1, 6, -7, 7, 10]

Check whether arr[i] = -arr[i-1].

Time complexity: O(nlogn)
Space complexity: O(1)

C++

Solution 3: Two Pointers

Sort the array.

Let sum = nums[i] + nums[j], sum == 0, we find one pair, if sum < 0, ++i else –j.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

花花酱 LeetCode 2418. Sort the People

By zxi on September 26, 2022

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the ith person.

Return names sorted in descending order by the people’s heights.

Example 1:

Input: names = ["Mary","John","Emma"], heights = [180,165,170]
Output: ["Mary","Emma","John"]
Explanation: Mary is the tallest, followed by Emma and John.

Example 2:

Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]
Output: ["Bob","Alice","Bob"]
Explanation: The first Bob is the tallest, followed by Alice and the second Bob.

Constraints:

  • n == names.length == heights.length
  • 1 <= n <= 103
  • 1 <= names[i].length <= 20
  • 1 <= heights[i] <= 105
  • names[i] consists of lower and upper case English letters.
  • All the values of heights are distinct.

Solution: Zip and sort

Time complexity: O(nlogn)
Space complexity: O(n)

C++