2023-12-06：用go语言，给你一个由 n 个数对组成的数对数组 pairs，其中 pairs[i] = [lefti,

福大大架构师每日一题

发布于 2023-12-13 11:30:33

1520

发布于 2023-12-13 11:30:33

文章被收录于专栏：福大大架构师每日一题

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;
}