假設我有以下物件的串列：
class Row{
int a;
int b;
}
資料的設定方式是，如果按 a 排序，資料會自動按 b 排序。我需要撰寫一個接受引數的函式，該函式(int x, List<Row> rows)找到 b 緊隨 x 之后的行。記錄數為 1000，因此基本且簡單的方法是按 a 排序，然后使用迭代找到最近的元素。有沒有另一種方式來構造資料，我不必遍歷整個串列？
uj5u.com熱心網友回復：
你可以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)
uj5u.com熱心網友回復：
最簡單的方法是從排序串列開始。串列排序后，您可以使用二進制搜索將可能的值減少到 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();
}
樣品運行：
Closest value to 17: 13
Closest value to 28: 13
Closest value to -26: -23
Closest value to 22: 13
Closest value to 0: 0
Closest value to -10: -3
Closest value to -11: -3
Closest value to -24: -23
Closest value to -33: -23
Closest value to -40: -23
Closest value to 15: 13
Closest value to 3: 3
Closest value to -26: -23
Closest value to -13: -21
Closest value to -6: -3
Closest value to 12: 13
Closest value to 43: 44
Closest value to -37: -23
Closest value to 1: 1
Closest value to 4: 5
Closest value to 10: 8
Closest value to 22: 13
Closest value to 7: 8
Closest value to -50: -23
Closest value to -20: -21
Closest value to -50: -23
Closest value to 25: 13
Closest value to 20: 13
Closest value to -31: -23
Closest value to -41: -23
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/524612.html
標籤：爪哇算法排序