Javascript:找出不按顺序的日期

Question

考虑这个嵌套的日期和名称数组:

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 而不是框架。 (我在节点中，但我正在寻找一个无包的解决方案，这样我就可以理解发生了什么......)

Answer 1

这是对 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));