考虑这个嵌套的日期和名称数组：
var fDates = [
['2015-02-03', 'name1'],
['2015-02-04', 'nameg'],
['2015-02-04', 'name5'],
['2015-02-05', 'nameh'],
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-07', 'name0'],
['2015-02-08', 'nameh'],
['2015-02-15', 'namex'],
['2015-02-09', 'namew'],
['1980-12-23', 'name2'],
['2015-02-12', 'namen'],
['2015-02-13', 'named'],
]
如何识别那些不按顺序排列的日期。我不在乎日期重复，或跳过，我只是需要那些不按顺序。即，我应该回来：
results = [
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-15', 'namex'],
['1980-12-23', 'name2'],
]
（'Namex'不太明显，但它不是列表的一般顺序。）
这似乎是最长增长子序列（LIS）问题的变化，但需要注意的是序列中可能有重复的日期，但不应该向后退一步。
使用案例：我已对记录进行了排序和记录，需要找到日期为“可疑”的日期 - 可能是输入错误 - 标记为检查。
NB1：我使用的是直接的Javascript而不是框架。 （我在节点，但我正在寻找一个无包装的解决方案，所以我可以理解发生了什么...）
这是Rosetta Code LIS的改编，采取自定义getElement和compare功能。我们可以根据您的特定需求优化比较和元素获取功能。
function f(arr, getElement, compare){
function findIndex(input){
var len = input.length;
var maxSeqEndingHere = new Array(len).fill(1)
for(var i=0; i<len; i++)
for(var j=i-1;j>=0;j--)
if(compare(getElement(input, i), getElement(input, j)) && maxSeqEndingHere[j] >= maxSeqEndingHere[i])
maxSeqEndingHere[i] = maxSeqEndingHere[j]+1;
return maxSeqEndingHere;
}
function findSequence(input, result){
var maxValue = Math.max.apply(null, result);
var maxIndex = result.indexOf(Math.max.apply(Math, result));
var output = new Set();
output.add(maxIndex);
for(var i = maxIndex ; i >= 0; i--){
if(maxValue==0)break;
if(compare(getElement(input, maxIndex), getElement(input, i)) && result[i] == maxValue-1){
output.add(i);
maxValue--;
}
}
return output;
}
var result = findIndex(arr);
var final = findSequence(arr, result)
return arr.filter((e, i) => !final.has(i));
}
var fDates = [
['2015-02-03', 'name1'],
['2015-02-04', 'nameg'],
['2015-02-04', 'name5'],
['2015-02-05', 'nameh'],
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-07', 'name0'],
['2015-02-08', 'nameh'],
['2015-02-15', 'namex'],
['2015-02-09', 'namew'],
['1980-12-23', 'name2'],
['2015-02-12', 'namen'],
['2015-02-13', 'named'],
];
console.log(f(fDates, (arr, i) => arr[i][0], (a,b) => a >= b));此解决方案尝试获取所有有效序列并返回最长序列以过滤掉部分。
它通过迭代给定的数组并检查值是否可以构建序列来工作。如果给出了一个值，哪个部分结果具有有效的前导，则该数组将附加该值。如果没有进行回溯并且使用有效的前任搜索序列。
act. array value 7 3 4 4 5 1 23 7 comment ----- ------------------------ --------------------------- 7 7 add array with single value 3 7 keep 3 add array with single value 4 7 keep 3 4 add value to array 4 7 keep 3 4 4 add value to array 5 7 keep 3 4 4 5 add value to array 1 7 keep 3 4 4 5 keep 1 add array with single value 23 7 23 add value to array 3 4 4 5 23 add value to array 1 23 add value to array 7 7 23 keep 7 7 fork above, filter for smaller or equal and add value 3 4 4 5 23 keep 3 4 4 5 7 fork above, filter for smaller or equal and add value 1 23 keep 1 7 fork above, filter for smaller or equal and add value
function longestSequences(array, getValue = v => v) {
return array
.reduce(function (sub, value) {
var single = true;
sub.forEach(function (s) {
var temp;
if (getValue(s[s.length - 1]) <= getValue(value)) {
s.push(value);
single = false;
return;
}
// backtracking
temp = s.reduceRight(function (r, v) {
if (getValue(v) <= getValue(r[0])) {
r.unshift(v);
single = false;
}
return r;
}, [value]);
if (temp.length !== 1 && !sub.some(s => s.length === temp.length && s.every((v, i) => getValue(v) === getValue(temp[i])))) {
sub.push(temp);
}
});
if (single) {
sub.push([value]);
}
return sub;
}, [])
.reduce(function (r, a) {
if (!r || r[0].length < a.length) {
return [a];
}
if (r[0].length === a.length) {
r.push(a);
}
return r;
}, undefined);
}
function notInSequence(array, getValue = v => v) {
var longest = longestSequences(array, getValue);
return array.filter((i => a => a !== longest[0][i] || !++i)(0));
}
var array = [7, 3, 4, 4, 5, 1, 23, 7, 8, 15, 9, 2, 12, 13],
fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
usuallyFailingButNotHere = [['2015-01-01'], ['2014-01-01'], ['2015-01-02'], ['2014-01-02'], ['2015-01-03'], ['2014-01-03'], ['2014-01-04'], ['2015-01-04'], ['2014-01-05'], ['2014-01-06'], ['2014-01-07'], ['2014-01-08'], ['2014-01-09'], ['2014-01-10'], ['2014-01-11']],
test2 = [['1975-01-01'], ['2015-02-03'], ['2015-02-04'], ['2015-02-04'], ['2015-02-05'], ['1929-03-12'], ['2023-07-01'], ['2015-02-07'], ['2015-02-08']];
console.log(longestSequences(array));
console.log(notInSequence(array));
console.log(notInSequence(fDates, a => a[0]));
console.log(longestSequences(usuallyFailingButNotHere, a => a[0]));
console.log(notInSequence(usuallyFailingButNotHere, a => a[0]));
console.log(longestSequences(test2, a => a[0]));
console.log(notInSequence(test2, a => a[0]));.as-console-wrapper { max-height: 100% !important; top: 0; }此解决方案使用函数reduce并保留先前接受的日期以进行必要的比较。
var fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
results = fDates.reduce((acc, c, i, arr) => {
/*
* This function finds a potential valid sequence.
* Basically, will check if any next valid sequence is
* ahead from the passed controlDate.
*/
function sequenceAhead(controlDate) {
for (var j = i + 1; j < arr.length; j++) {
let [dt] = arr[j];
//The controlDate is invalid because at least a forward date is in conflict with its sequence.
if (dt > acc.previous && dt < controlDate) return true;
}
//The controlDate is valid because forward dates don't conflict with its sequence.
return false;
}
let [date] = c; //Current date in this iteration.
if (i > 0) { // If this is not the first iteration
if (date === acc.previous) return acc; // Same as previous date are skipped.
// If the current date is lesser than previous then is out of sequence.
// Or if there is at least valid sequence ahead.
if (date < acc.previous || sequenceAhead(date)) acc.results.push(c);
else acc.previous = date; // Else, this current date is in sequence.
}
else acc.previous = date; // Else, set the first date.
return acc;
}, { 'results': [] }).results;
console.log(results);.as-console-wrapper { max-height: 100% !important; top: 0; }以前的所有答案都集中在JavaScript上，可能它们无法正常工作。所以我决定添加专注于算法的新答案。
正如@ Trees4theForest在他的问题和评论中提到的，他正在寻找Longest Increase Subsequence和out of order dates的解决方案是不在最长增长子序列（LIS）集中的日期。
我使用下面的this方法。从算法的角度来看，这是真的。
function longestIncreasingSequence(arr, strict) {
var index = 0,
indexWalker,
longestIncreasingSequence,
i,
il,
j;
// start by putting a reference to the first entry of the array in the sequence
indexWalker = [index];
// Then walk through the array using the following methodolgy to find the index of the final term in the longestIncreasing and
// a sequence (which may need altering later) which probably, roughly increases towards it - http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
for (i = 1, il = arr.length; i < il; i++) {
if (arr[i] < arr[indexWalker[index]]) {
// if the value is smaller than the last value referenced in the walker put it in place of the first item larger than it in the walker
for (j = 0; j <= index; j++) {
// As well as being smaller than the stored value we must either
// - be checking against the first entry
// - not be in strict mode, so equality is ok
// - be larger than the previous entry
if (arr[i] < arr[indexWalker[j]] && (!strict || !j || arr[i] > arr[indexWalker[j - 1]])) {
indexWalker[j] = i;
break;
}
}
// If the value is greater than [or equal when not in strict mode) as the last in the walker append to the walker
} else if (arr[i] > arr[indexWalker[index]] || (arr[i] === arr[indexWalker[index]] && !strict)) {
indexWalker[++index] = i;
}
}
// Create an empty array to store the sequence and write the final term in the sequence to it
longestIncreasingSequence = new Array(index + 1);
longestIncreasingSequence[index] = arr[indexWalker[index]];
// Work backwards through the provisional indexes stored in indexWalker checking for consistency
for (i = index - 1; i >= 0; i--) {
// If the index stored is smaller than the last one it's valid to use its corresponding value in the sequence... so we do
if (indexWalker[i] < indexWalker[i + 1]) {
longestIncreasingSequence[i] = arr[indexWalker[i]];
// Otherwise we need to work backwards from the last entry in the sequence and find a value smaller than the last entry
// but bigger than the value at i (this must be possible because of the way we constructed the indexWalker array)
} else {
for (j = indexWalker[i + 1] - 1; j >= 0; j--) {
if ((strict && arr[j] > arr[indexWalker[i]] && arr[j] < arr[indexWalker[i + 1]]) ||
(!strict && arr[j] >= arr[indexWalker[i]] && arr[j] <= arr[indexWalker[i + 1]])) {
longestIncreasingSequence[i] = arr[j];
indexWalker[i] = j;
break;
}
}
}
}
return longestIncreasingSequence;
}
使用上面的方法，我们可以找到无序的日期，如下所示：
// Finding Longest Increase Subsequence (LIS) set
var _longestIncreasingSequence = longestIncreasingSequence(fDates.map(([date]) => date));
// Out of order dates
var result = fDates.filter(([date]) => !_longestIncreasingSequence.includes(date));
这是一个简单的不言自明的解决方案。希望它会对你有所帮助。
const findOutOfSequenceDates = items => {
items = items.map(d => d);
const sequence = [], outOfsequence = [];
sequence.push(items.shift());
const last = ind => sequence[sequence.length - ind][0];
items.forEach(item => {
const current = new Date(item[0]);
if (current >= new Date(last(1))) {
sequence.push(item);
} else if (current >= new Date(last(2))) {
outOfsequence.push(sequence.pop());
sequence.push(item);
} else {
outOfsequence.push(item);
}
});
return outOfsequence;
};
var fDates = [
['2015-02-03', 'name1'],
['2015-02-04', 'nameg'],
['2015-02-04', 'name5'],
['2015-02-05', 'nameh'],
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-07', 'name0'],
['2015-02-08', 'nameh'],
['2015-02-15', 'namex'],
['2015-02-09', 'namew'],
['1980-12-23', 'name2'],
['2015-02-12', 'namen'],
['2015-02-13', 'named'],
];
console.log(findOutOfSequenceDates(fDates));使用Javascript Date type。与这些对象比较。非常简单，
date1 = new Date(fDates[i, 0])
date2 = new Date(fDates[i+1, 0])
if (date2 < date1) { // or whatever comparison you want ...
// flag / print / alert the date
}
澄清一下，这只是不按顺序找到项目。正如Jaromanda X所指出的，你可以用字符串来做到这一点。但是，您使用短语“out out line”;无论这对你意味着什么，Date应该让你有能力确定和测试它。例如，'2023-07-01'是不可接受的，因为距离它还有8年，或者仅仅是因为它与2015年的日期有关？您可能需要对更简单的时间跨度进行一些比较，例如一个月，您的比较看起来就像
if (date2-date1 > one_month)
您的问题摘要如果我已正确理解您的问题，您将尝试根据时间/日期属性值识别不遵循时间顺序的数组条目。
解决方案将日期字符串/时间转换为UNIX时间戳（自01 / jan / 1970 00:00:00以来经过的秒数）
使用循环，我们可以将值存储在每个读数的先前读数中，如果值为负，这将表示日期过去时出现错误，如果值为正，则表示订单有效
当为负数时，我们可以创建一个数组来表示引用数组的位置及其值，使您可以返回到原始数组并查看数据。
示例代码
var arrData = [
{date: '2015-02-03', value:'name1'},
{date: '2015-02-04', value:'nameg'},
{date: '2015-02-04', value:'name5'},
{date: '2015-02-05', value:'nameh'},
{date: '1929-03-12', value:'name4'},
{date: '2023-07-01', value:'name7'},
{date: '2015-02-07', value:'name0'},
{date: '2015-02-08', value:'nameh'},
{date: '2015-02-15', value:'namex'},
{date: '2015-02-09', value:'namew'},
{date: '1980-12-23', value:'name2'},
{date: '2015-02-12', value:'namen'},
{date: '2015-02-13', value:'named'}
];
var arrSeqErrors = [];
function funTestDates(){
var intLastValue = 0, intUnixDate =0;
for (x = 0; x <= arrData.length-1; x++){
intUnixDate = Date.parse(arrData[x].date)/1000;
var intResult = intUnixDate - intLastValue;
if (intResult < 0){
console.log("initeneration: " + x + " is out of sequence");
arrSeqErrors.push (arrData[x]);
}
intLastValue = intResult;
}
console.log("Items out of sequence are:");
console.log(arrSeqErrors);
}
funTestDates();