从给定模式中选取m个不同对象的最快方法是什么？

Question

给定一个由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元素使用递归，并尝试与连续颜色结合的所有组合。

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。

- David Naga

---

乍一看这似乎是一个动态规划问题。你可以通过记忆化的方式进行优化。 - Emily

@Emily 动态规划使用递归还是迭代？ - David Naga

无所谓，两种方式基本上是等价的（如果我没记错的话）。 - Emily

预期时间复杂度为O(n) - 你是这样期望的还是任务分配者期望的？ - tevemadar

@tevemadar 我预计会是这样，但是 n log n 也可以接受，我想。 - David Naga

Answer 1

我们可以用时间复杂度为O(n log n)，空间复杂度为O(n)的方法解决这个问题。首先注意到，任何分配的颜色都必须距离其相邻颜色的元素m个元素，否则会违反约束条件。

将每个由它们之间的距离定义的具有相同颜色的元素列表（仅）分开，并对它们进行排序。

现在将所有m个排序列表合并成一个排序列表，其中每个值还与它来自的列表的颜色标签配对（例如，合并的列表可以是元组）。

（或者，我们可以首先创建整个带标签的列表，然后只对该列表进行排序。）

使用大小为m的滑动窗口迭代有标签的排序列表，在任何时候仅允许一个颜色的元素留在窗口中。 （我们可以使用哈希映射或简单数组来跟踪窗口。请记住，在此情况下，窗口指的是唯一标签的窗口，而不是标签列表的连续子数组）。 在迭代过程中更新窗口中存在的最小范围以确定答案。

- גלעד ברקן

Answer 2

我认为你可以对数字进行排序（但要保持它们的颜色），然后从开头开始遍历结果，首先增加一个候选项以包含所有颜色（因此head将覆盖子列表中的唯一颜色），然后缩小它，使重复的颜色从tail中删除（因此它将指向唯一的颜色），然后检查是否是迄今为止最佳的候选项，然后丢弃tail（因此该颜色将不再出现），再次从头开始：

import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class NewClass {
    public static void doThing(int nums[],int m){
        int n=nums.length;
        ColorNumber l[]=new ColorNumber[n];
        for(int i=0;i<n;i++)
            l[i]=new ColorNumber(nums[i], i%m);
        System.out.println(Arrays.asList(l));
        Arrays.sort(l, null);
        List printlist=Arrays.asList(l);
        System.out.println(printlist);
        int present[]=new int[m];
        int head=0,tail=0;
        int minhead=0,mintail=0,mindiff=Integer.MAX_VALUE;
        while(head<n){
            System.out.println("try growing");
            int i=0;
            while(i<m && head<n){
                while(present[i]==0 && head<n){
                    present[l[head].color]++;
                    head++;
                }
                //if(present[i]>0)i++;           // the bug
                while(i<m && present[i]>0)i++;   // the fix
            }
            if(i==m){
                System.out.println(printlist.subList(tail, head));
                System.out.println("try shrinking");
                while(present[l[tail].color]>1){
                    present[l[tail].color]--;
                    tail++;
                }
                int diff=l[head-1].number-l[tail].number;
                System.out.println(printlist.subList(tail, head)+" diff: "+diff);
                if(diff<mindiff){minhead=head;mintail=tail;mindiff=diff;}
                present[l[tail].color]--;
                tail++;
            }
        }
        System.out.println("min: "+mindiff+", "+printlist.subList(mintail, minhead));
    }

    static class ColorNumber implements Comparable<ColorNumber>{
        final int number;
        final int color;

        public ColorNumber(int number, int color) {
            this.number = number;
            this.color = color;
        }

        @Override
        public int compareTo(ColorNumber o) {
            return number-o.number;
        }

        @Override
        public String toString() {
            return number+"("+color+")";
        }
    }

    public static void main(String args[]){
        Random r=new Random(0);
        int nums[]=new int[10];
        for(int i=0;i<nums.length;i++)
            nums[i]=r.nextInt(100);
        doThing(nums, 3);
        System.out.println("---");
        doThing(new int[]{10,20,15,28},2);
        System.out.println("---");
        doThing(new int[] {2,1},2);              // test case for bug
    }
}

输出内容（一个由种子提供的三色常数随机序列，您的双色示例和您修复的错误测试用例）：

[60(0), 48(1), 29(2), 47(0), 15(1), 53(2), 91(0), 61(1), 19(2), 54(0)]
[15(1), 19(2), 29(2), 47(0), 48(1), 53(2), 54(0), 60(0), 61(1), 91(0)]
try growing
[15(1), 19(2), 29(2), 47(0)]
try shrinking
[15(1), 19(2), 29(2), 47(0)] diff: 32
try growing
[19(2), 29(2), 47(0), 48(1)]
try shrinking
[29(2), 47(0), 48(1)] diff: 19
try growing
[47(0), 48(1), 53(2)]
try shrinking
[47(0), 48(1), 53(2)] diff: 6
try growing
[48(1), 53(2), 54(0)]
try shrinking
[48(1), 53(2), 54(0)] diff: 6
try growing
[53(2), 54(0), 60(0), 61(1)]
try shrinking
[53(2), 54(0), 60(0), 61(1)] diff: 8
try growing
min: 6 [47(0), 48(1), 53(2)]
---
[10(0), 20(1), 15(0), 28(1)]
[10(0), 15(0), 20(1), 28(1)]
try growing
[10(0), 15(0), 20(1)]
try shrinking
[15(0), 20(1)] diff: 5
try growing
min: 5 [15(0), 20(1)]
---
[2(0), 1(1)]
[1(1), 2(0)]
try growing
[1(1), 2(0)]
try shrinking
[1(1), 2(0)] diff: 1
min: 1, [1(1), 2(0)]

在输出中，只有最低值和最高值的颜色将是唯一的，中间的元素可以任意选择，因为它们不会对差异产生影响（该代码像第一个序列中的最后一次尝试一样将它们全部输出([53(2), 54(0), 60(0), 61(1)])）。如果需要特定的输出，可以使用一些Set或者用for循环遍历颜色，仅打印每种颜色的一个元素（并跳过其余的元素，使用简单的break语句）。

- tevemadar

---

并没有什么不同。你描述了一个在按值排序的列表上滑动的唯一着色窗口。这正是我提出的想法。（你说得对，我没有建议具体的实现方式。） - גלעד ברקן

@גלעדברקן 在你的描述中，“使用大小为m的滑动窗口遍历已排序的标记列表，同时只允许一个颜色的元素留在窗口中”非常模糊。我从未说过它是固定大小的窗口（实际上不是），也没有说它包含每种颜色的一个元素（因为当有重复颜色时，在“tail”上需要最高值，在“head”上需要最低值-因此需要跟踪一个颜色的多个值）。对于我来说，只有“head”和“tail”是唯一的，我不关心它们之间的部分，正如我最后所说的那样。 - tevemadar

@tevemadar，你的代码在一些测试用例中失败了（答案错误），但我无法找出原因。有什么想法吗？ - David Naga

@DavidNaga 所以它被发送到某个自动评估器。它期望什么输出格式？ - tevemadar

@tevemadar 我找到错误了！！！这一行 "if(present[i]>0)i++;" 是错的。你需要将其改为 while 循环。应该是 "while(i < m && present[i]>0) { i++; }" - David Naga