|
/**
* ShortestSubsequence.cpp
* @Author Tu Yongce
* @Created 2008-6-7
* @Modified 2008-6-7
* @Version 0.1
*/
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/*
* 判断目标序列（非负整数序列）中是否存在一个其和大于等于指定阈值的子序列
* 如果存在这样的子序列，找出满足此条件的一个最短子序列
* @param data: 存储目标序列的数组首指针
* @param num: 数组大小（序列中元素个数）
* @param threshold: 阈值
* @param start: [out]如果存在满足条件的子序列，返回最短子序列的起始元素下标
* @param end: [out]如果存在满足条件的子序列，返回最短子序列的终止元素下标
* @return: 如果存在满足条件的子序列，返回true且子序列为[start, end]；
* 否则，返回false
* @note: 算法时间复杂度为O（n)，序列中每个元素都多扫描两次
*/
static bool ShortestSubsequence(size_t data[], size_t num, size_t threshold,
size_t &start, size_t &end)
{
assert(num > 0 && threshold > 0);
// 标记满足条件的子序列是否存在
bool found = false;
// 初始子序列
size_t first = 0;
size_t len = 0;
size_t sum = 0;
for (size_t i = 0; i < num;) {
// 向后搜索满足条件的子序列
while (i < num && sum < threshold) {
sum += data[i++];
++len;
}
if (sum < threshold)
break; // 当前子序列之和小于阈值（已达到目标序列尾）
// 修正（尽量缩短）当前满足条件的子序列
while (sum - data[first] >= threshold) {
sum -= data[first++];
--len;
}
if (!found || len < end - start + 1) {
start = first; // 更新最短子序列
end = i - 1;
found = true;
}
// 去掉当前满足条件的子序列最前一个或者两个（如果有两个的话）元素，
// 形成新的子序列，继续向后搜索
sum -= data[first++];
--len;
if (len > 0) {
sum -= data[first++];
--len;
}
}
return found;
}
static void Test(size_t testNum, size_t data[], size_t num, size_t threshold)
{
cout << "Test " << testNum << ":\n";
cout << ">>\nSequence: [";
copy(data, data + num, ostream_iterator<size_t>(cout, " "));
cout << "]\n";
cout << "Threshold: " << threshold << endl;
size_t minStart, minEnd;
bool exist = ShortestSubsequence(data, num, threshold, minStart, minEnd);
if (exist)
cout << "Found：[" << minStart << ", " << minEnd << "]\n";
else
cout << "Not Found\n";
cout << "<<\n" << endl;
}
void ShortestSubsequence_Test()
{
size_t data1[] = {5};
size_t num1 = sizeof(data1) / sizeof(data1[0]);
size_t threshold1 = 5;
Test(1, data1, num1, threshold1);
size_t data2[] = {5};
size_t num2 = sizeof(data2) / sizeof(data2[0]);
size_t threshold2 = 6;
Test(2, data2, num2, threshold2);
size_t data3[] = {5, 8, 4, 7, 10, 5, 2};
size_t num3 = sizeof(data3) / sizeof(data3[0]);
size_t threshold3 = 18;
Test(3, data3, num3, threshold3);
size_t data4[] = {5, 8, 4, 7, 10, 5, 17, 10};
size_t num4 = sizeof(data4) / sizeof(data4[0]);
size_t threshold4 = 18;
Test(4, data4, num4, threshold4);
size_t data5[] = {5, 8, 4, 7, 10, 5, 12, 18};
size_t num5 = sizeof(data5) / sizeof(data5[0]);
size_t threshold5 = 18;
Test(5, data5, num5, threshold5);
}
|
