2023-12-06：用go语言，给你一个由 n 个数对组成的数对数组 pairs， 其中 pairs[i] = [lefti,
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]?
})
ends?:=?make([]int,?n)
size?:=?0
for?_,?pair?:=?range?pairs?{
l,?r?:=?0,?size-1
m,?find?:=?0,?-1
for?l?
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)?->?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?
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![vec![1,?2],?vec![2,?3],?vec![3,?4]];
let?result?=?find_longest_chain(pairs);
println!("{}",?result);
}
在这里插入图片描述c++完整代码如下：
#include?
#include?
#include?
int?findLongestChain(std::vector&?pairs)?{
int?n?=?pairs.size();
std::sort(pairs.begin(),?pairs.end(),?[](const?std::vector&?a,?const?std::vector&?b)?{
return?a[0]?
});
std::vector?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?
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?pairs{?{1,2},?{2,3},?{3,4}?};
int?result?=?findLongestChain(pairs);
std::cout?
return?0;
}
在这里插入图片描述c完整代码如下：
#include?
#include?
int?findLongestChain(int**?pairs,?int?pairsSize,?int*?pairsColSize)?{
//?根据第一列排序
for?(int?i?=?0;?i?
for?(int?j?=?0;?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?
int?l?=?0;
int?r?=?size?-?1;
int?m?=?0;
int?find?=?-1;
while?(l?
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]?
}
}
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;
}
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OXqvW1OBIM_eiCrUGvQRUfaQ0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
