php - 如何选择日期差异最小的行

Question

这个问题很难表述。希望这是有道理的。

我的库存中有一张元素表。

让我们称这些项目为 Apple、Orange、Pear、Potato。我想挑一篮子水果(1 个苹果、1 个橙子、1 个梨)。

库存中的每个项目都有不同的可用日期。这样……

1. 苹果 1 月
2. 苹果二月
3. 苹果三月
4. 橙色 4 月
5. Apple 4 月
6. 梨 5 月

我不想按照元素在库存中出现的顺序挑选元素。相反，我想根据可以选择所有项目的最小日期范围来选择它们。即 4 月的橙子和苹果以及 5 月的梨。

我不确定这是否是 MYSQL 或某些 PHP 数组的问题。我很难过。提前致谢。

Answer 1

如果水果数组尚未按日期排序，让我们对其进行排序。

现在，简单的 O(n^2) 解决方案是检查所有可能的范围。没有特定语言的伪代码:

for (int i = 0; i < inventory.length; ++i)
    hash basket = {}
    for (int j = i; j < inventory.length; ++j) {
        basket.add(inventory[j]);
        if (basket.size == 3) { // or whatever's the number of fruits
            // found all fruits
            // compare range [i, j] with the best range
            // update best range, if necessary
            break;
        }
    }
end

您可能会发现它已经足够好了。
或者您可以编写更复杂的 O(n) 解决方案。它只是一个滑动窗口[first, last]。在每一步中，我们移动左边界(从篮子中排除一个水果)或右边界(向篮子中添加一个水果)。

int first = 0;
int last = 0;
hash count = {};
count[inventory[0]] = 1;

while (true) {
    if (count[inventory[first]] > 0) {
        --count[inventory[first]];
        ++first;
    } else if (last < inventory.length) {
        ++last;
        ++count[inventory[last]];
    } else {
        break;
    }

    if (date[last] - date[first] < min_range
            && count.number_of_nonzero_elements == 3) {
        // found new best answer
        min_range = date[last] - date[first]
    }
}