如何提高算法的时间复杂度以找到数组中整数的最长连续子序列
How to improve time complexity of algorithm to find the longest consecutive subsequence of integers in an array
有多种方法可以解决 codeforces 问题 F. Consecutive Subsequence:
You are given an integer array of length
You have to choose some subsequence of this array of maximum length such that this subsequence forms a increasing sequence of consecutive integers. In other words the required sequence should be equal to [,+1,…,+−1] for some value and length .
Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array [5,3,1,2,4] the following arrays are subsequences: [3], [5,3,1,2,4], [5,1,4], but the array [1,3] is not.
我尝试过的一种不使用动态规划的方法的 Python 代码如下所示。为避免重复，if 语句检查数组中是否存在比当前数字小的数字，因为这样可以包含它以增加子序列的长度。
A = [3, 3, 4, 7, 5, 6, 8]
def longestConsecutive(nums):
longest_streak = 0 #length of longest consecutive subsequence of integers
indices = []
for i in range(1,len(nums)):
b = set(nums[0:i])
if nums[i-1] - 1 not in b:
indices.append(i)
current_num = nums[i-1]
current_streak = 1
k = i
for j in range(k, len(nums)):
if A[j] == current_num + 1:
indices.append(j+1)
current_num += 1
current_streak += 1
k=j
if current_streak < longest_streak:
indices = indices[0:len(indices)-current_streak] #remove the current_streak's indices
else:
longest_streak = current_streak
return [longest_streak,indices[len(indices)-longest_streak:len(indices)]]
c = longestConsecutive(A)
print(c[0])
print(*c[1])
我认为这个算法的时间复杂度是 O(n) 因为第二个 for 循环最多运行 n 次而第一个 for 循环运行 n-1 次并且每次查找都是 O(1) 因为集合 b用来。这在解决不同但相关问题的 on LeetCode 中进行了解释，因为我的代码是对所讨论的第三种算法的修改。所有其他计算都需要常数时间。尽管如此，该算法还是通过了测试 1-4 但未通过测试 5，其中输入数组的大小为 200000，并且超过了 2 秒的时间限制。问题是复杂性实际上更大吗？有人看到如何优化代码吗？
我觉得递归函数更容易理解和遵循。基本上你只想检查你当前的步骤是否比以前更好，如果不是，则继续前进。我相信排序的部分也可以做得更快，因为显然没有必要完全排序才能得出我们有一个非连续序列的结论。我留给你改进：
def f(x,n=1):
if len(x)<n:
return
elif x[:n]==sorted(x[:n]):
a = f(x,n+1)
return x[:n] if a is None else a
return f(x[1:],n)
您的算法具有 O(²) 时间复杂度。
集合的创建已经花费了 O(1) + O(2) + ... + O() = O(²) 时间。尽管您可以通过将新值添加到现有集合中来避免这种情况（而不是从头开始重建它），但内部循环仍然会使时间复杂度呈二次方变化，这无法通过简单调整算法来解决。 indices[0:len(indices)-current_streak] 中发生的切片也会影响时间复杂度。
我看不出有什么方法可以调整这个算法来提高它的时间复杂度，我认为需要一种完全不同的方法。
另一种方法
一个可能的解决方案具有 O() 时间复杂度——如果我们假设字典操作的 amortised 时间复杂度是 O(1)——是一个您跟踪序列在字典中的结束位置，并为该结束点存储结束于此的序列的大小。
例如，如果我们到目前为止已经确定了一个从 5 开始到 8 结束的序列，它将在该字典中用 { 8: 3 }.
表示
然后，当从输入列表中读取下一个值时，当它还不是该字典中的键时，我们可以检查它是否在高端扩展了一个序列。然后更新字典来表示新情况就很简单了。
当所有值都这样处理后，剩下的就是使用该字典识别最长的序列。
这个想法的 Python 实现可以在这个剧透中找到：
def longestConsecutive(nums):
if not nums: # Boundary case: empty list
return 0, []
size_for_end = {}
for value in nums:
if value not in size_for_end:
if value - 1 in size_for_end:
# This value extends a sequence
size_for_end[value] = size_for_end.pop(value - 1) + 1
else:
# This is a new sequence with just one value
size_for_end[value] = 1
# All sequences have been identified, so get the longest
size, end = max((size, end) for end, size in size_for_end.items())
return size, list(range(end - size + 1, end + 1))
注意：相关的LeetCode问题可以通过使用两个字典而不是一个字典来解决，其中第二个字典引用相同的序列，但是从starting值的角度来看该序列，以便每个序列都由两个词典中的一个条目表示。
这里的问题是找到一个高效的算法。
建议创建一个索引数组 (0 2 3 ... n-1)，并根据 A[index] 的值对它们进行排序。
排序必须稳定，才能正确管理重复项。例如，只有第一个副本值得保留。
在遍历排序的索引时，如果有一次我们发现一个索引较低但值较高的元素，则必须在第一步中忽略该元素。但是，它的值必须要记住，以便以后再回来就可以了。
复杂度由排序决定，即O(nlogn)。
这是一个 C++ 代码来说明算法。
输出处的索引是零索引的（C++ 样式）。只需添加 +1 即可获得 1 索引索引。
输出：
1 3 5 2 4 6 -> 2 [0 3] -> values: 1 2
10 9 8 7 -> 1 [3] -> values: 7
6 7 8 3 4 5 9 10 11 -> 6 [0 1 2 6 7 8] -> values: 6 7 8 9 10 11
5 2 3 6 7 4 8 0 9 -> 5 [0 3 4 6 8] -> values: 5 6 7 8 9
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
void print (const std::vector<int> &A, const std::string &after = "\n", const std::string &before = "") {
std::cout << before;
int n = A.size();
for (int i = 0; i < n; ++i) {
std::cout << A[i];
if (i != n-1) std::cout << " ";
}
std::cout << after;
}
std::vector<int> long_subseq (std::vector<int>& A) {
std::vector<int> seq, seq_opt;
int n = A.size();
if (n == 0) return seq_opt;
if (n == 1) {
return std::vector<int> (1, 0);
}
std::vector<int> indices(n);
std::iota (indices.begin(), indices.end(), 0);
auto fsort = [&] (int i, int j) {return A[i] < A[j];};
std::stable_sort (indices.begin(), indices.end(), fsort);
seq.push_back (indices[0]);
seq_opt.push_back (indices[0]);
int max_length = 1;
int length = 1;
int last_index = indices[0];
int next_index = -1;
for (int i = 1; i < n; ++i) {
//std::cout << "i = " << i << "\n";
if (A[indices[i]] == A[last_index]) continue;
if ((last_index < indices[i]) && (A[indices[i]] == A[last_index] + 1)) {
length++;
seq.push_back (indices[i]);
last_index = indices[i];
} else {
if (indices[i] < last_index) {
if (next_index == -1) next_index = i;
}
if (A[indices[i]] > A[last_index] + 1) {
if (length > max_length) {
max_length = length;
std::swap (seq_opt, seq);
}
length = 1;
seq.resize(0);
if (next_index != -1) {
last_index = indices[next_index];
i = next_index - 1;
next_index = -1;
} else {
last_index = indices[i];
}
seq.push_back (last_index);
}
}
}
if (length > max_length) {
max_length = length;
std::swap (seq_opt, seq);
}
return seq_opt;
}
int main() {
std::vector<std::vector<int>> examples = {
{1, 3, 5, 2, 4, 6},
{10, 9, 8, 7},
{6, 7, 8, 3, 4, 5, 9, 10, 11},
{5, 2, 3, 6, 7, 4, 8, 0, 9}
};
for (auto &A: examples) {
auto ans = long_subseq (A);
print (A, " -> ");
std::cout << ans.size() << " ";
print (ans, "] -> values: ", "[");
for (int i = 0; i < ans.size(); ++i) {
std::cout << A[ans[i]] << " ";
}
std::cout << "\n";
}
return 0;
}
有多种方法可以解决 codeforces 问题 F. Consecutive Subsequence:
You are given an integer array of length
You have to choose some subsequence of this array of maximum length such that this subsequence forms a increasing sequence of consecutive integers. In other words the required sequence should be equal to [,+1,…,+−1] for some value and length .
Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array [5,3,1,2,4] the following arrays are subsequences: [3], [5,3,1,2,4], [5,1,4], but the array [1,3] is not.
我尝试过的一种不使用动态规划的方法的 Python 代码如下所示。为避免重复，if 语句检查数组中是否存在比当前数字小的数字，因为这样可以包含它以增加子序列的长度。
A = [3, 3, 4, 7, 5, 6, 8]
def longestConsecutive(nums):
longest_streak = 0 #length of longest consecutive subsequence of integers
indices = []
for i in range(1,len(nums)):
b = set(nums[0:i])
if nums[i-1] - 1 not in b:
indices.append(i)
current_num = nums[i-1]
current_streak = 1
k = i
for j in range(k, len(nums)):
if A[j] == current_num + 1:
indices.append(j+1)
current_num += 1
current_streak += 1
k=j
if current_streak < longest_streak:
indices = indices[0:len(indices)-current_streak] #remove the current_streak's indices
else:
longest_streak = current_streak
return [longest_streak,indices[len(indices)-longest_streak:len(indices)]]
c = longestConsecutive(A)
print(c[0])
print(*c[1])
我认为这个算法的时间复杂度是 O(n) 因为第二个 for 循环最多运行 n 次而第一个 for 循环运行 n-1 次并且每次查找都是 O(1) 因为集合 b用来。这在解决不同但相关问题的 on LeetCode 中进行了解释，因为我的代码是对所讨论的第三种算法的修改。所有其他计算都需要常数时间。尽管如此，该算法还是通过了测试 1-4 但未通过测试 5，其中输入数组的大小为 200000，并且超过了 2 秒的时间限制。问题是复杂性实际上更大吗？有人看到如何优化代码吗？
我觉得递归函数更容易理解和遵循。基本上你只想检查你当前的步骤是否比以前更好，如果不是，则继续前进。我相信排序的部分也可以做得更快，因为显然没有必要完全排序才能得出我们有一个非连续序列的结论。我留给你改进：
def f(x,n=1):
if len(x)<n:
return
elif x[:n]==sorted(x[:n]):
a = f(x,n+1)
return x[:n] if a is None else a
return f(x[1:],n)
您的算法具有 O(²) 时间复杂度。
集合的创建已经花费了 O(1) + O(2) + ... + O() = O(²) 时间。尽管您可以通过将新值添加到现有集合中来避免这种情况（而不是从头开始重建它），但内部循环仍然会使时间复杂度呈二次方变化，这无法通过简单调整算法来解决。 indices[0:len(indices)-current_streak] 中发生的切片也会影响时间复杂度。
我看不出有什么方法可以调整这个算法来提高它的时间复杂度，我认为需要一种完全不同的方法。
另一种方法
一个可能的解决方案具有 O() 时间复杂度——如果我们假设字典操作的 amortised 时间复杂度是 O(1)——是一个您跟踪序列在字典中的结束位置，并为该结束点存储结束于此的序列的大小。
例如，如果我们到目前为止已经确定了一个从 5 开始到 8 结束的序列，它将在该字典中用 { 8: 3 }.
然后，当从输入列表中读取下一个值时，当它还不是该字典中的键时，我们可以检查它是否在高端扩展了一个序列。然后更新字典来表示新情况就很简单了。
当所有值都这样处理后，剩下的就是使用该字典识别最长的序列。
这个想法的 Python 实现可以在这个剧透中找到：
def longestConsecutive(nums): if not nums: # Boundary case: empty list return 0, [] size_for_end = {} for value in nums: if value not in size_for_end: if value - 1 in size_for_end: # This value extends a sequence size_for_end[value] = size_for_end.pop(value - 1) + 1 else: # This is a new sequence with just one value size_for_end[value] = 1 # All sequences have been identified, so get the longest size, end = max((size, end) for end, size in size_for_end.items()) return size, list(range(end - size + 1, end + 1))
注意：相关的LeetCode问题可以通过使用两个字典而不是一个字典来解决，其中第二个字典引用相同的序列，但是从starting值的角度来看该序列，以便每个序列都由两个词典中的一个条目表示。
这里的问题是找到一个高效的算法。
建议创建一个索引数组 (0 2 3 ... n-1)，并根据 A[index] 的值对它们进行排序。
排序必须稳定，才能正确管理重复项。例如，只有第一个副本值得保留。
在遍历排序的索引时，如果有一次我们发现一个索引较低但值较高的元素，则必须在第一步中忽略该元素。但是，它的值必须要记住，以便以后再回来就可以了。
复杂度由排序决定，即O(nlogn)。
这是一个 C++ 代码来说明算法。
输出处的索引是零索引的（C++ 样式）。只需添加 +1 即可获得 1 索引索引。
输出：
1 3 5 2 4 6 -> 2 [0 3] -> values: 1 2
10 9 8 7 -> 1 [3] -> values: 7
6 7 8 3 4 5 9 10 11 -> 6 [0 1 2 6 7 8] -> values: 6 7 8 9 10 11
5 2 3 6 7 4 8 0 9 -> 5 [0 3 4 6 8] -> values: 5 6 7 8 9
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
void print (const std::vector<int> &A, const std::string &after = "\n", const std::string &before = "") {
std::cout << before;
int n = A.size();
for (int i = 0; i < n; ++i) {
std::cout << A[i];
if (i != n-1) std::cout << " ";
}
std::cout << after;
}
std::vector<int> long_subseq (std::vector<int>& A) {
std::vector<int> seq, seq_opt;
int n = A.size();
if (n == 0) return seq_opt;
if (n == 1) {
return std::vector<int> (1, 0);
}
std::vector<int> indices(n);
std::iota (indices.begin(), indices.end(), 0);
auto fsort = [&] (int i, int j) {return A[i] < A[j];};
std::stable_sort (indices.begin(), indices.end(), fsort);
seq.push_back (indices[0]);
seq_opt.push_back (indices[0]);
int max_length = 1;
int length = 1;
int last_index = indices[0];
int next_index = -1;
for (int i = 1; i < n; ++i) {
//std::cout << "i = " << i << "\n";
if (A[indices[i]] == A[last_index]) continue;
if ((last_index < indices[i]) && (A[indices[i]] == A[last_index] + 1)) {
length++;
seq.push_back (indices[i]);
last_index = indices[i];
} else {
if (indices[i] < last_index) {
if (next_index == -1) next_index = i;
}
if (A[indices[i]] > A[last_index] + 1) {
if (length > max_length) {
max_length = length;
std::swap (seq_opt, seq);
}
length = 1;
seq.resize(0);
if (next_index != -1) {
last_index = indices[next_index];
i = next_index - 1;
next_index = -1;
} else {
last_index = indices[i];
}
seq.push_back (last_index);
}
}
}
if (length > max_length) {
max_length = length;
std::swap (seq_opt, seq);
}
return seq_opt;
}
int main() {
std::vector<std::vector<int>> examples = {
{1, 3, 5, 2, 4, 6},
{10, 9, 8, 7},
{6, 7, 8, 3, 4, 5, 9, 10, 11},
{5, 2, 3, 6, 7, 4, 8, 0, 9}
};
for (auto &A: examples) {
auto ans = long_subseq (A);
print (A, " -> ");
std::cout << ans.size() << " ";
print (ans, "] -> values: ", "[");
for (int i = 0; i < ans.size(); ++i) {
std::cout << A[ans[i]] << " ";
}
std::cout << "\n";
}
return 0;
}