如何找到最小范围

Question

我有一张java地图：

 Map<String, ArrayList<Integer>> positions = new HashMap<String, ArrayList<Integer>>();

这张地图基本上包含：

 word1: 2 10 17 
 word2: 3  8 15 20
 word3: 6  9 19 22
 word4: 7 12 18 24
 ..... and so on

现在我想找到所有单词位置之间的最小范围。我们将拥有唯一且排序的位置（即没有两个整数相同）。

The minimum range here is 3 (between 10, 8, 9 and 7)

我们应该如何解决这个问题？

I thought of the following steps:

    1) Have pointers as many as words length.
    2) In this example, we have 4 pointers, pointing towards 2, 3, 6 and 7.
    3) The range is calculated which comes out be 5.
    4) Keep this range in a certain variable say 'min'.
    5) Repeat until all positions in all lists have not been read:
        a) Move the lowest pointer to the next in the list(In this example, we move pointer-1 to point to 10).
        b) Calculate the range again (this comes to be 7 now).
        c) If the new range < min:
             min = new range
    6) Return 'min'

但我不知道如何在 Java 中解决这个问题。有人可以帮帮我吗？如果你有什么不同的做法，我会很欢迎。

Answer 1

这是我想出的解决方案（是用 C# 编写的，但基本思想应该可以转移到 Java）

public class RangeFinder
{
    public List<List<int>> WordList { get; set; }
    public List<int> IndexList { get; private set; }

    public int MinRange()
    {
        IndexList = new List<int>();
        for (int i = 0; i < WordList.Count; i++)
        {
            IndexList.Add(0);
        }
        int min = Int32.MaxValue;
        do
        {
            var range = CalculateRange();
            if (range < min)
            {
                min = range;
            }
        }
        while (!EndReached());
        return min;
    }

    private int CalculateRange()
    {
        var maxVal = Int32.MinValue;
        var minVal = Int32.MaxValue;
        for (int i = 0; i < WordList.Count; i++)
        {
            var word = WordList[i];
            var val = word[IndexList[i]];
            if(val > maxVal)
            {
                maxVal = val;
            }
            if(val < minVal)
            {
                minVal = val;
            }
        }
        return maxVal - minVal;
    }

    private bool EndReached()
    {
        for(int i=0; i < IndexList.Count; i++)
        {
            var word = WordList[i];
            var wordCount = word.Count;
            IndexList[i] = (++IndexList[i]) % wordCount;
            if(IndexList[i] > 0)
            {
                return false;
            }
        }
        return true;
    }
}

其工作原理的简要概述：创建 class 时会填充 WordList（对于 Java，创建填充 WordList 的构造函数）。在我的测试代码中，我刚刚为每个单词创建了一个列表，并列出了每个单词。 IndexList 跟踪我们正在查看每个单词的数字。它们都从索引 0 开始。然后，我们递增第一个单词。当第一个词的索引回绕时，我们增加第二个词。当第二个词的索引回绕时，我们增加第三个词。这一直持续到最后一个词的索引换行。发生这种情况时，我们知道所有可能的组合都已查看，我们可以 return 最小范围。

如何找到最小范围

How to find the minimum range

list

range

minimum