149. 直线上最多的点数
标题链接
149. 直线上最多的点数
标签
多少 数组 哈希表 数学
思路
总体思路
本题是一道 数学题，可以采取 暴力 的方式：
- 先 罗列所有由两点连接而成的直线，即 罗列任意两个点 计算其所在直线。
- 然后再 罗列所有点，统计 每条直线上的点的数量 的最大值。
可以轻微对这种方式进行优化：
- 将第一步中的 罗列任意两个点 改为 罗列 任意点 和 其之后的所有点。防止 计算完点 A A A 和点 B B B 所在直线上的点的数量之后，再计算点 B B B 和点 A A A 所在直线上的点的数量 如许的重复计算。
- 将第二步中的 罗列所有点 改为 罗列 第一步罗列的两个点之后的 所有点。制止了重复计算。
如何判断 一个点 在 由两点确定的直线 上
接下来就需要思量如何判断一个点 在 由两点确定的直线 上，其实并不难，既然已经罗列出两个点 P 1 ( x 1 , y 1 ) , P 2 ( x 2 , y 2 ) P_1(x_1, y_1), P_2(x_2, y_2) P1(x1,y1),P2(x2,y2)，对于第三个点 P 3 ( x 3 , y 3 ) P_3(x_3, y_3) P3(x3,y3)，只要 第一个点 和 第二个点 所确定直线的斜率 与 第二个点 和 第三个点 所确定直线的斜率 雷同，则点 P 3 P_3 P3 在直线 P 1 P 2 P_1P_2 P1P2 上。斜率雷同可以表现如下：
x 1 − x 2 y 1 − y 2 = x 2 − x 3 y 2 − y 3 \frac{x_1 - x_2}{y_1 - y_2} = \frac{x_2 - x_3}{y_2 - y_3} y1−y2x1−x2=y2−y3x2−x3
但是，在程序中无法使用 int, double 表现分数，如果强行使用，则会造成一定的精度丧失，导致结果错误。以是思量 将 除法 酿成 乘法，斜率雷同表现如下：
( y 2 − y 3 ) ( x 1 − x 2 ) = ( x 2 − x 3 ) ( y 1 − y 2 ) (y_2 - y_3) (x_1 - x_2) = (x_2 - x_3) (y_1 - y_2) (y2−y3)(x1−x2)=(x2−x3)(y1−y2)
确定第三个点是否在直线上时，需要多次使用 ( x 1 − x 2 ) (x_1 - x_2) (x1−x2) 和 ( y 1 − y 2 ) (y_1 - y_2) (y1−y2)，以是用变量来纪录它们： Δ x = ( x 1 − x 2 ) , Δ y = ( y 1 − y 2 ) \Delta x = (x_1 - x_2), \Delta y = (y_1 - y_2) Δx=(x1−x2),Δy=(y1−y2)，斜率雷同表现如下：
( y 2 − y 3 ) Δ x = ( x 2 − x 3 ) Δ y (y_2 - y_3) \Delta x = (x_2 - x_3) \Delta y (y2−y3)Δx=(x2−x3)Δy
代码
- class Solution {
- public int maxPoints(int[][] points) {
- int n = points.length; // 获取数组中点的数量
- if (n <= 2) { // 如果点的数量小于等于 2
- return 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 个高频元素
标签
数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）
思路
本题可以使用 优先队列，和 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. 下一个排列
标签
数组 双指针
思路
本题是 纯技巧题，只要会这个技巧便能解决本题，如果不会，最好将其 背 下来。这个技巧分为如下三步：
- 寻找：
- 在数组中，从右向左寻找 小于它右边的数 的数，将其称为 逆数。例如 [1, 2, 5, 4, 6, 3] 中的 4。
- 如果在数组中找到了 逆数，那么从 末了一个数 到 逆数 的下一个数，寻找一个 比 逆数 大 的数，将其称为 大数。例如 [1, 2, 5, 4, 6, 3] 中的 6。
- 互换：如果能找到 大数，则互换这两个数。
- 反转：
- 如果在数组中找到了 逆数，则将 逆数 的下一个数 到 末了一个数 的范围内的所有数进行反转操作。
- 如果在数组中没有找到 逆数，则将整个数组都进行反转操作。
如果很难理解这个技巧，不妨来看看这个例子，至少知道它可以使用：
- 对于数组 [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--;
- }
- }
- }
|
