给定一个由n个元素组成的数组,其中每个元素在2到10^5的范围内。现在,如果我们对数组的元素进行涂色,使得对于每个m(m <= n)个连续的元素,没有两个元素具有相同的颜色。我该如何选择M个不同的元素(不一定是连续的),以便所选元素中没有两个具有相同的颜色,并且所选元素中最大元素和最小元素之间的差异最小?
例如:对于n = 4,A={10 20 15 28} m = 2,我们可以将元素涂成R G R G或G R G R。 在这两种情况下,如果我们选择任何m个连续元素,则没有两个元素具有相同的颜色,例如R G或G R或R G。 有4种选择2个元素的方法,即10 20或10 28或20 15或15 28。但是20-15=5,这是最好的答案。
**数组中允许重复元素
我的方法是首先将所有相同颜色的元素放入单独的数组中。就像上面的例子中,我可以做:[[10,15][20,28]],其中10和15是R,20和28是G。然后我对每个R元素使用递归,并尝试与连续颜色结合的所有组合。
例如:对于n = 4,A={10 20 15 28} m = 2,我们可以将元素涂成R G R G或G R G R。 在这两种情况下,如果我们选择任何m个连续元素,则没有两个元素具有相同的颜色,例如R G或G R或R G。 有4种选择2个元素的方法,即10 20或10 28或20 15或15 28。但是20-15=5,这是最好的答案。
**数组中允许重复元素
我的方法是首先将所有相同颜色的元素放入单独的数组中。就像上面的例子中,我可以做:[[10,15][20,28]],其中10和15是R,20和28是G。然后我对每个R元素使用递归,并尝试与连续颜色结合的所有组合。
void recurse(List<List<Integer>> bs, int max, int min, int depth) {
if(depth == bs.size()) {
int diference = max - min;
// compare diff with old res here
return;
}
for(int i=0;i<bs.get(depth).size();++i) {
int newMax = Math.max(max,bs.get(depth).get(i));
int newMin = Math.min(min,bs.get(depth).get(i));
recurse(bs, newMax, newMin, depth+1);
}
}
这并没有错误,且能够产生正确的结果。但我正在寻找一个更快的算法。期望的时间复杂度为O(n),或者更好地说,我想在1秒内通过每个测试用例。请注意,2 <= m <= n <= 10^5。