class Solution {
public:
vector<int> longestCommonSubsequence(vector<vector<int>>& arrays) {
}
};
1940. 排序数组之间的最长公共子序列
给定一个由整数数组组成的数组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 <= 1001 <= arrays[i].length <= 1001 <= arrays[i][j] <= 100arrays[i] 是严格递增排序.原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 43.6 MB, 提交时间: 2023-10-17 12:01:16
class Solution {
public List<Integer> longestCommonSubsequence(int[][] arrays) {
int[] cnt = new int[101];
List<Integer> ans = new ArrayList<Integer>();
int n = arrays.length;
for ( int[] a: arrays ) {
for ( int v: a ) {
cnt[v]++;
}
}
for (int i = 0; i < 101; ++i ) {
if ( cnt[i] == n ) {
ans.add(i);
}
}
return ans;
}
}
rust 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2023-10-17 11:55:40
impl Solution {
pub fn longest_common_subsequence(arrays: Vec<Vec<i32>>) -> Vec<i32> {
let n = arrays.len();
let mut freq = [0; 101];
(0..n).for_each(|i| (0..arrays[i].len()).for_each(|j| freq[arrays[i][j] as usize] += 1));
(0..101).filter(|&i| freq[i] as usize == n).map(|i| i as i32).collect()
}
}
golang 解法, 执行用时: 28 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-17 11:54:47
func longestCommonSubsequence(arrays [][]int) (ans []int) {
cnt := [101]int{}
for _, a := range arrays {
for _, v := range a {
cnt[v]++
}
}
for v, c := range cnt {
if c == len(arrays) {
ans = append(ans, v)
}
}
return
}
cpp 解法, 执行用时: 28 ms, 内存消耗: 17 MB, 提交时间: 2023-10-17 11:54:14
class Solution {
public:
vector<int> longestCommonSubsequence(vector<vector<int>>& arrays) {
map<int,int> mp;
int n = arrays.size();
for(auto x:arrays){
for(int y:x){
mp[y]++;
}
}
vector<int> ans;
for(auto z:mp){
if(z.second==n){ans.push_back(z.first);}
}
return ans;
}
};
python3 解法, 执行用时: 56 ms, 内存消耗: 16.7 MB, 提交时间: 2023-10-17 11:53:31
class Solution:
def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
counter = [0] * 101
n = len(arrays)
res = []
for i in range(n):
for j in arrays[i]:
counter[j] += 1
for i in range(101):
if counter[i] == n: res.append(i)
return res