LeetCode 149, 347, 31

---

149. 直线上最多的点数

题目链接

149. 直线上最多的点数

标签

几何 数组 哈希表 数学

思路

总体思路

本题是一道 数学题，可以采取 暴力 的方式：

• 先 枚举所有由两点连接而成的直线，即 枚举任意两个点 计算其所在直线。
• 然后再 枚举所有点，统计 每条直线上的点的数量 的最大值。

可以稍微对这种方式进行优化：

• 将第一步中的 枚举任意两个点 改为 枚举 任意点 和 其之后的所有点。防止 计算完点 $A$ 和点 $B$ 所在直线上的点的数量之后，再计算点 $B$ 和点 $A$ 所在直线上的点的数量 这样的重复计算。
• 将第二步中的 枚举所有点 改为 枚举 第一步枚举的两个点之后的 所有点。避免了重复计算。

如何判断 一个点 在 由两点确定的直线 上

接下来就需要考虑如何判断一个点 在 由两点确定的直线 上，其实并不难，既然已经枚举出两个点 $P_1(x_1,y_1),P_2(x_2,y_2)$，对于第三个点 $P_3(x_3,y_3)$，只要 第一个点 和 第二个点 所确定直线的斜率 与 第二个点 和 第三个点 所确定直线的斜率 相同，则点 $P_3$ 在直线 $P_1{P}_2$ 上。斜率相同可以表示如下：
$$\frac{x_1-x_2}{y_1-y_2}=\frac{x_2-x_3}{y_2-y_3}$$
但是，在程序中无法使用 int, double 表示分数，如果强行使用，则会造成一定的精度损失，导致结果错误。所以考虑 将 除法 变成 乘法，斜率相同表示如下：
$$(y_2-y_3)(x_1-x_2)=(x_2-x_3)(y_1-y_2)$$
确定第三个点是否在直线上时，需要多次使用 $(x_1-x_2)$ 和 $(y_1-y_2)$，所以用变量来记录它们：$\Delta x=(x_1-x_2),\Delta y=(y_1-y_2)$，斜率相同表示如下：
$$(y_2-y_3)\Delta x=(x_2-x_3)\Delta y$$

代码

class Solution {public int maxPoints(int[][] points) {int n = points.length; // 获取数组中点的数量if (n <= 2) { // 如果点的数量小于等于 2return n; // 则直接返回点的数量即可}int res = 0; // 保存结果for (int i = 0; i < n; i++) {int[] p1 = points[i]; // 第一个点for (int j = i + 1; j < n; j++) {int[] p2 = points[j]; // 第二个点int deltaX = p1[0] - p2[0]; // p1 和 p2 的横坐标的差值int deltaY = p1[1] - p2[1]; // p1 和 p2 的纵坐标的差值// 统计有多少个点位于 p1 与 p2 所确定的直线上，初始值为 2 表示 p1 和 p2 位于这条直线上int cnt = 2;for (int k = j + 1; k < n; k++) {int[] p3 = points[k]; // 第三个点// 如果 p3 在 p1, p2 所确定的直线上，则点数加一if ((p3[1] - p2[1]) * deltaX == (p3[0] - p2[0]) * deltaY) {cnt++;}}res = Math.max(res, cnt); // 更新最大值}}return res;}
}

347. 前 K 个高频元素

题目链接

347. 前 K 个高频元素

标签

数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）

思路

本题可以使用 优先队列，和 LeetCode 215. 数组中的第K个最大元素 很相似，都使用 小顶堆 来存放数组中优先级前 K 高的元素，不过本题中元素的优先级不是元素的值，而是元素的出现次数。

本题直接使用 Java 中的 PriorityQueue 优先队列，（用一个长度为 2 的数组作为类型参数）保存元素的值和出现次数。此外，需要在构造器中传入一个 比较器，定义优先队列内部存储的数据如何进行比较。

代码

class Solution {public int[] topKFrequent(int[] nums, int k) {// 统计每个元素出现的次数，key 为元素的值，value 为元素出现的次数Map<Integer, Integer> cnt = new HashMap<>(nums.length);for (int num : nums) {cnt.put(num, cnt.getOrDefault(num, 0) + 1);}// 小顶堆，元素出现的次数越少，越靠近顶部。存放着数组中频率前 k 高的元素// 在 int[] 中存放了 2 个值，第一个值表示 元素的值，第二个值表示 元素出现的次数PriorityQueue<int[]> pq = new PriorityQueue<>((p1, p2) -> p1[1] - p2[1]);for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) { // 构建小顶堆int num = entry.getKey(), count = entry.getValue();if (pq.size() < k) { // 如果小顶堆中的元素少于 k 个pq.offer(new int[]{num, count}); // 则给其中添加元素} else if (count > pq.peek()[1]) {// 此时元素个数等于 k 个，如果 当前元素的出现次数 大于 堆顶元素的出现次数pq.poll(); // 则移除堆顶元素pq.offer(new int[]{num, count}); // 将当前元素放入堆中}}// 构造结果数组并返回int[] res = new int[k];for (int i = 0; i < k; i++) {res[i] = pq.poll()[0];}return res;}
}

31. 下一个排列

题目链接

31. 下一个排列

标签

数组 双指针

思路

本题是 纯技巧题，只要会这个技巧便能解决本题，如果不会，最好将其 背 下来。这个技巧分为如下三步：

1. 寻找：
   • 在数组中，从右向左寻找 小于它右边的数 的数，将其称为 逆数。例如 [1, 2, 5, 4, 6, 3] 中的 4。
   • 如果在数组中找到了 逆数，那么从 最后一个数 到 逆数 的下一个数，寻找一个 比 逆数 大 的数，将其称为 大数。例如 [1, 2, 5, 4, 6, 3] 中的 6。
2. 交换：如果能找到 大数，则交换这两个数。
3. 反转：
   • 如果在数组中找到了 逆数，则将 逆数 的下一个数 到 最后一个数 的范围内的所有数进行反转操作。
   • 如果在数组中没有找到 逆数，则将整个数组都进行反转操作。

如果很难理解这个技巧，不妨来看看这个例子，至少知道它可以使用：

对于数组 [1, 2, 5, 4, 6, 3]
-----------------------------------
寻找逆数和比逆数大的数，分别用 i, j 指向：
[1, 2, 5, 4, 6, 3]^  ^i  j
-----------------------------------
交换 i, j 指向的数：
[1, 2, 5, 6, 4, 3]^i
-----------------------------------
反转 i + 1 之后的部分：
[1, 2, 5, 6, 3, 4]

代码

class Solution {public void nextPermutation(int[] nums) {final int n = nums.length;// 从右往左扫描，直到找到一个 比它右边的数小的 数int i = n - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}// 如果在数组中找到了逆数if (i >= 0) {// 则 在 索引为 i + 1 的数 到 最后一个数 的范围内，寻找一个比逆数大的数int j = n - 1;while (j > i && nums[i] >= nums[j]) {j--;}// 交换它们swap(nums, i, j);}// 反转 i + 1 之后的部分reverse(nums, i + 1);}// 交换 nums 中索引 i, j 指向的元素private void swap(int[] nums, int i, int j) {int temp  = nums[i];nums[i] = nums[j];nums[j] = temp;}// 从 start 开始反转 nums 数组private void reverse(int[] nums, int start) {int left = start, right = nums.length - 1;while (left < right) {swap(nums, left, right);left++;right--;}}
}