Skip to content

Latest commit

 

History

History
208 lines (167 loc) · 5.37 KB

README.md

File metadata and controls

208 lines (167 loc) · 5.37 KB
comments difficulty edit_url tags
true
中等
数组
哈希表
计数

1940. 排序数组之间的最长公共子序列 🔒

English Version

题目描述

给定一个由整数数组组成的数组 arrays，其中 arrays[i] 是 严格递增 排序的，返回一个 所有 数组均包含的 最长公共子序列 的整数数组。

子序列 是从另一个序列派生出来的序列，删除一些元素或不删除任何元素，而不改变其余元素的顺序。

示例1:

输入: arrays = [[1,3,4],
               [1,4,7,9]]
输出: [1,4]
解释: 这两个数组中的最长子序列是[1,4]。

示例 2:

输入: arrays = [[2,3,6,8],
               [1,2,3,5,6,7,10],
               [2,3,4,6,9]]
输出: [2,3,6]
解释: 这三个数组中的最长子序列是 [2,3,6]。

示例 3:

输入: arrays = [[1,2,3,4,5],
               [6,7,8]]
输出: []
解释: 这两个数组之间没有公共子序列。

 

限制条件:

  • 2 <= arrays.length <= 100
  • 1 <= arrays[i].length <= 100
  • 1 <= arrays[i][j] <= 100
  • arrays[i] 是严格递增排序.

解法

方法一：计数

我们注意到，元素的范围是 $[1, 100]$，我们可以用一个长度为 $101$ 的数组 $\textit{cnt}$ 来记录每个元素出现的次数。

由于数组 $\textit{arrays}$ 中的每个数组都是严格递增排序的，因此，公共子序列的元素必然是单调递增，并且这些元素的出现次数都等于 $\textit{arrays}$ 的长度。

因此，我们可以遍历 $\textit{arrays}$ 中的每个数组，统计每个元素的出现次数，最后，从小到大遍历 $\textit{cnt}$ 的每个元素，如果出现次数等于 $\textit{arrays}$ 的长度，那么这个元素就是公共子序列的元素之一，我们将其加入答案数组中。

遍历结束后，返回答案数组即可。

时间复杂度 $O(M + N)$，空间复杂度 $O(M)$。其中 $M$ 为元素的范围，本题中 $M = 101$，而 $N$ 为数组所有元素的个数。

Python3

class Solution:
    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
        cnt = [0] * 101
        for row in arrays:
            for x in row:
                cnt[x] += 1
        return [x for x, v in enumerate(cnt) if v == len(arrays)]

Java

class Solution {
    public List<Integer> longestCommonSubsequence(int[][] arrays) {
        int[] cnt = new int[101];
        for (var row : arrays) {
            for (int x : row) {
                ++cnt[x];
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < 101; ++i) {
            if (cnt[i] == arrays.length) {
                ans.add(i);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> longestCommonSubsequence(vector<vector<int>>& arrays) {
        int cnt[101]{};
        for (const auto& row : arrays) {
            for (int x : row) {
                ++cnt[x];
            }
        }
        vector<int> ans;
        for (int i = 0; i < 101; ++i) {
            if (cnt[i] == arrays.size()) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

Go

func longestCommonSubsequence(arrays [][]int) (ans []int) {
	cnt := [101]int{}
	for _, row := range arrays {
		for _, x := range row {
			cnt[x]++
		}
	}
	for x, v := range cnt {
		if v == len(arrays) {
			ans = append(ans, x)
		}
	}
	return
}

TypeScript

function longestCommonSubsequence(arrays: number[][]): number[] {
    const cnt: number[] = Array(101).fill(0);
    for (const row of arrays) {
        for (const x of row) {
            ++cnt[x];
        }
    }
    const ans: number[] = [];
    for (let i = 0; i < 101; ++i) {
        if (cnt[i] === arrays.length) {
            ans.push(i);
        }
    }
    return ans;
}

JavaScript

/**
 * @param {number[][]} arrays
 * @return {number[]}
 */
var longestCommonSubsequence = function (arrays) {
    const cnt = Array(101).fill(0);
    for (const row of arrays) {
        for (const x of row) {
            ++cnt[x];
        }
    }
    const ans = [];
    for (let i = 0; i < 101; ++i) {
        if (cnt[i] === arrays.length) {
            ans.push(i);
        }
    }
    return ans;
};