7

考虑一些long被调用X和排序的List<Long>。找到(i)小于和(ii)数轴上最接近的索引或值的最有效算法是什么List<Long>（假设条件 (i) 已满足）？XX

例如，这可能是一个问题设置：

long X = 500;
List<Long> foo = new Arraylist<Long>();
foo.add(450L);
foo.add(451L);    
foo.add(499L);
foo.add(501L);
foo.add(550L);

Collections.sort(foo); // It's always sorted.

我希望算法返回499或返回与499（在这种情况下i=2）关联的索引。

4

3 回答 3

17

鉴于您列表中的值是唯一的，我建议您使用 a Set，更具体地说是 a TreeSet，因为无论如何您都在对列表进行排序。您可以使用NavigableSet#floor(E)完全符合您要求的方法。

返回此集合中小于或等于给定元素的最大元素，或者null如果没有这样的元素。

因此，代码如下所示：

long X = 500;
NavigableSet<Long> foo = new TreeSet<Long>();

foo.add(450L);
foo.add(451L);    
foo.add(499L);
foo.add(501L);
foo.add(550L);

System.out.println(foo.floor(X));   // 499

该方法也适用于用户定义的对象。只需在实例化它时将 a 传递Comparator<YourClass>给构造函数。TreeSet

于 2013-10-05T13:59:33.520 回答
6

Collections.binarySearch您可以为此使用 java ，因为您的列表已排序。

在spec中，二分查找返回：

搜索关键字的索引，如果它包含在列表中；否则，（-（插入点）- 1）。插入点定义为将键插入列表的点：第一个元素的索引大于键，如果列表中的所有元素都小于指定的键，则为 list.size()。请注意，这保证了当且仅当找到键时，返回值将 >= 0。

首先，如果你进行二分搜索并且元素在列表中，你会得到一个正值（元素的索引），并且可以返回它（或者如果你仍然想要一个更少的元素，你可以向后走从那里直到你找到一个）。

否则，如果您搜索不在列表中的内容，您可以从返回值向后工作到您想要的索引。如果您在示例列表中搜索 500，算法将返回 (-3 - 1) = -4。因此，您可以添加 1 以返回到插入点 (-3)，然后乘以 -1 并减去 1 以获得第一个元素之前的索引，该索引大于您搜索的那个，这将是一个索引如果列表中的所有元素都大于您搜索的元素，则满足您的 2 个条件或 -1。

在树集上使用二分搜索的优点是它的开销可能会更少。

于 2013-10-05T14:25:12.047 回答
5

/*查找列表中最接近的数字 * @param list of Integers * @param num 找到最接近的数字 * @return Closest number * */

public static int findClosestNumber(List list, int num) {
    if (list.size() > 0) { // Check list does not empty
        int smaller =
            (Integer)Collections.min(list); // get min number from the list
        int larger =
            (Integer)Collections.max(list); // get max number from the list

        for (int i = 0; i < list.size(); i++) { //Traverse list
            if (num == (Integer)list.get(i))   //if find the passed number in the list
                return num;                     //than return num
            if (num > (Integer)list.get(i) && smaller < (Integer)list.get(i)) // find nearest smaller
                smaller = (Integer)list.get(i);
            if (num < (Integer)list.get(i) && larger > (Integer)list.get(i)) // find nearest larger
                larger = (Integer)list.get(i);
        }
        return (num - smaller < larger - num ? smaller : larger); // return closest number
    }
return 0;
}

}

于 2014-11-22T22:42:49.843 回答