java 在以下情况下,如何在列表中找到最接近的值?

6rqinv9w  于 2022-10-30  发布在  Java
关注(0)|答案(2)|浏览(315)

让我们假设我有一个包含以下对象的列表:

class Row{
   int a;
   int b;
}

数据的设置方式是:如果按a排序,数据将自动按b排序。我需要编写一个函数,该函数接受参数(int x, List<Row> rows),以查找b紧跟在x之后的行。记录数为1000,因此基本且简单的方法是按a排序,然后使用迭代查找最近的元素。有没有其他方法来构造数据,而不必遍历整个列表?

vbkedwbf

vbkedwbf1#

最简单的方法是从一个排序的列表开始。一旦列表被排序,你可以使用二进制搜索将可能的值减少到2,而不是像你通常在搜索时所做的那样寻找一个完全匹配。
您需要做的另一件事是建立两个基本案例,这将帮助您避免索引越界问题:这两种情况是,

  • 如果该值小于或等于列表中的最小数字,则返回list(0)。
  • 如果该值大于或等于列表中的最大数字,则返回list(size - 1)。

一旦基本情况都试过了,就可以简单地使用折半搜索将你的选择减少到两个值,然后你所需要做的就是比较实际值和存储在列表中两个选择的索引中的数字之间的差的绝对值。

public class ClosestInteger {
    public static void main(String[] args) {

        List<Integer> values = List.of(-23, -21, -3, 0, 1, 2, 3, 5, 8, 13, 44);

        for (int i = 0; i < 10; i++) {
            Random rand = new Random();
            int value = rand.nextInt(-50, 50);
            System.out.println("Closest value to " + value + ": " + closestValue(values, value));
        }
    }

    private static int closestValue(List<Integer> list, int value) {
        if (list== null || list.isEmpty()) {
            throw new IllegalArgumentException("List cannot be null or empty");
        }

        if (value <= list.get(0)) {
            return list.get(0);
        }

        if (value >= list.get(list.size() - 1)) {
            return list.get(list.size() - 1);
        }

        int left = 0, right = list.size() - 1, mid = 0;

        while (left <= right) {
            mid = left + (right - left) / 2;

            if (list.get(mid) == value)
                return value;

            if (list.get(mid) < value) {
                left = mid + 1;
            }

            else {
                right = mid - 1;
            }
        }

        return  Math.abs(value - list.get(left)) <= Math.abs(value - list.get(right)) ? list.get(left) : list.get(right);
    }
}

我提出了下面的lambda函数来查找最接近的整数(尽管,它可能比上面的- O(n)?-慢)

private static int closestValue(List<Integer> list, int value) {
    return list.stream()
        .sorted(Comparator.comparingInt(i -> Math.abs(i - value)))
        .limit(1).findFirst().get();
}

样品运行:
第一个

qmelpv7a

qmelpv7a2#

您可以像这样使用Collections.binarySearch()

static class Row {
    int a, b; 
    public int getA() { return a; } 
    public int getB() { return b; } 
    Row(int a, int b) { this.a = a; this.b = b; } 
    @Override public String toString() { return "Row(" + a + ", " + b + ")"; }
}

static final Comparator<Row> ORDER_BY_B = Comparator.comparing(Row::getB);

static Row find(int x, List<Row> rows) {
    int size = rows.size();
    int i = Collections.binarySearch(rows, new Row(0, x), ORDER_BY_B);
    int index = i >= 0 ? i : i <= -size - 1 ? size - 1 : -i - 1;
    return rows.get(index);
}

public static void main(String[] args) {
    List<Row> rows = Arrays.asList(
        new Row(20, 2),
        new Row(40, 4),
        new Row(50, 5),
        new Row(70, 7));
    List<Row> orderByB = rows.stream().sorted(ORDER_BY_B).collect(Collectors.toList());
    for (int i = 0; i < 9; ++i)
        System.out.println("find " + i + " : " + find(i, orderByB));
}

输出:

find 0 : Row(20, 2)
find 1 : Row(20, 2)
find 2 : Row(20, 2)
find 3 : Row(40, 4)
find 4 : Row(40, 4)
find 5 : Row(50, 5)
find 6 : Row(70, 7)
find 7 : Row(70, 7)
find 8 : Row(70, 7)

相关问题