2023-12-06：用 go 语言，给你一个由 n 个数对组成的数对数组 pairs，
其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，
数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面，
我们用这种形式来构造 数对链。
找出并返回能够形成的 最长数对链的长度。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
输入：pairs = [[1,2], [2,3], [3,4]]。
输出：2。
答案 2023-12-06：
灵捷3.5
大体步骤如下：
1.首先对数对数组 pairs 按照左边界进行排序，确保数对按照左边界的升序排列。
2.创建一个大小为 n 的整型数组 ends，用于存储当前数对链中每个数对的右边界值。
3.初始化变量 size 为 0，表示当前数对链的长度。
4.遍历排序后的数对数组 pairs：
对于每个数对 pair，使用二分搜索找到 ends 数组中第一个大于等于 pair[0] 的索引 find。
如果找不到这样的索引，则将 pair[1] 添加到 ends 数组末尾，并将 size 加一。
如果找到了索引 find，则更新 ends[find] 的值为 min(ends[find], pair[1])。这是因为我们要构建最长数对链，所以应该选择右边界更小的数对。
5.返回变量 size 即为能够形成的最长数对链长度。
总的时间复杂度：在排序和遍历过程中，都需要 O(n log n) 的时间复杂度（排序花费 O(n log n)，遍历花费 O(n)）。而二分搜索操作也需要 O(log n) 的时间复杂度。所以总体上是 O(n log n)。
总的额外空间复杂度：除了存储输入数据之外，我们额外使用了一个大小为 n 的数组 ends 来存储数对链的右边界。因此，额外空间复杂度是 O(n)。
go 完整代码如下：
package main
import ( "fmt" "sort")
func findLongestChain(pairs [][]int) int { n := len(pairs) sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] < pairs[j][0] }) ends := make([]int, n) size := 0 for _, pair := range pairs { l, r := 0, size-1 m, find := 0, -1 for l <= r { m = (l + r) / 2 if ends[m] >= pair[0] { find = m r = m - 1 } else { l = m + 1 } } if find == -1 { ends[size] = pair[1] size++ } else { if ends[find] > pair[1] { ends[find] = pair[1] } } } return size}
func main() { pairs := [][]int{{1,2}, {2,3}, {3,4}} result := findLongestChain(pairs) fmt.Println(result)}
复制代码
rust 完整代码如下：
fn find_longest_chain(pairs: Vec<Vec<i32>>) -> i32 { let mut pairs = pairs; pairs.sort_by(|a, b| a[0].cmp(&b[0]));
let n = pairs.len() as i32; let mut ends = vec![0; n as usize]; let mut size: i32 = 0;
for pair in &pairs { let (mut l, mut r) = (0, size - 1); let (mut m, mut find) = (0, -1);
while l <= r { m = (l + r) / 2;
if ends[m as usize] >= pair[0] { find = m; r = m - 1; } else { l = m + 1; } }
if find == -1 { ends[size as usize] = pair[1]; size += 1; } else { ends[find as usize] = ends[find as usize].min(pair[1]); } }
size as i32}
fn main() { let pairs: Vec<Vec<i32>> = vec![vec![1, 2], vec![2, 3], vec![3, 4]]; let result = find_longest_chain(pairs); println!("{}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <algorithm>
int findLongestChain(std::vector<std::vector<int>>& pairs) { int n = pairs.size(); std::sort(pairs.begin(), pairs.end(), [](const std::vector<int>& a, const std::vector<int>& b) { return a[0] < b[0]; });
std::vector<int> ends(n, 0); int size = 0;
for (const auto& pair : pairs) { int l = 0; int r = size - 1; int m = 0; int find = -1;
while (l <= r) { m = (l + r) / 2;
if (ends[m] >= pair[0]) { find = m; r = m - 1; } else { l = m + 1; } }
if (find == -1) { ends[size++] = pair[1]; } else { ends[find] = std::min(ends[find], pair[1]); } }
return size;}
int main() { std::vector<std::vector<int>> pairs{ {1,2}, {2,3}, {3,4} };
int result = findLongestChain(pairs);
std::cout << result << std::endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>
int findLongestChain(int** pairs, int pairsSize, int* pairsColSize) { // 根据第一列排序 for (int i = 0; i < pairsSize; i++) { for (int j = 0; j < pairsSize - i - 1; j++) { if (pairs[j][0] > pairs[j + 1][0]) { int* temp = pairs[j]; pairs[j] = pairs[j + 1]; pairs[j + 1] = temp; } } }
int* ends = (int*)malloc(sizeof(int) * pairsSize); int size = 0;
for (int i = 0; i < pairsSize; i++) { int l = 0; int r = size - 1; int m = 0; int find = -1;
while (l <= r) { m = (l + r) / 2;
if (ends[m] >= pairs[i][0]) { find = m; r = m - 1; } else { l = m + 1; } }
if (find == -1) { ends[size++] = pairs[i][1]; } else { ends[find] = ends[find] < pairs[i][1] ? ends[find] : pairs[i][1]; } }
free(ends);
return size;}
int main() { // 输入数据 int pair_1[] = { 1, 2 }; int pair_2[] = { 2, 3 }; int pair_3[] = { 3, 4 };
int* pairs[] = { pair_1, pair_2, pair_3 }; int pairsSize = sizeof(pairs) / sizeof(pairs[0]); int pairsColSize[] = { 2, 2, 2 };
int result = findLongestChain(pairs, pairsSize, pairsColSize); printf("%d\n", result);
return 0;}
复制代码
![2023-12-06：用go语言，给你一个由 n 个数对组成的数对数组 pairs， 其中 pairs[i] = [lefti, righti] 且 lefti ＜ righti 。 现在，我们定义一_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论