Tìm giá trị gần nhất trong danh sách đơn đặt hàng

Question

Tôi tự hỏi bạn sẽ viết một phương thức java đơn giản như thế nào để tìm số nguyên trong tủ quần áo cho một giá trị đã cho trong danh sách Số nguyên được sắp xếp.

Đây là nỗ lực đầu tiên của tôi:

public class Closest { 

    private static List<Integer> integers = new ArrayList<Integer>(); 

    static { 
     for (int i = 0; i <= 10; i++) { 
      integers.add(Integer.valueOf(i * 10)); 
     } 
    } 

    public static void main(String[] args) { 

     Integer closest = null; 
     Integer arg = Integer.valueOf(args[0]); 

     int index = Collections.binarySearch(
       integers, arg); 

     if (index < 0) /*arg doesn't exist in integers*/ { 
      index = -index - 1; 
      if (index == integers.size()) { 
       closest = integers.get(index - 1); 
      } else if (index == 0) { 
       closest = integers.get(0); 
      } else { 
       int previousDate = integers.get(index - 1); 
       int nextDate = integers.get(index); 
       if (arg - previousDate < nextDate - arg) { 
        closest = previousDate; 
       } else { 
        closest = nextDate; 
       } 
      } 
     } else /*arg exists in integers*/ { 
      closest = integers.get(index); 
     } 
     System.out.println("The closest Integer to " + arg + " in " + integers 
       + " is " + closest); 
    } 
} 

Bạn nghĩ gì về giải pháp này? Tôi chắc chắn có một cách sạch hơn để thực hiện công việc này ...

Có lẽ phương pháp này tồn tại ở đâu đó trong thư viện Java và tôi đã bỏ lỡ nó?

Manu

Answer 1

thử phương pháp này ít:

public int closest(int of, List<Integer> in) { 
    int min = Integer.MAX_VALUE; 
    int closest = of; 

    for (int v : in) { 
     final int diff = Math.abs(v - of); 

     if (diff < min) { 
      min = diff; 
      closest = v; 
     } 
    } 

    return closest; 
} 

một số testcases:

private final static List<Integer> list = Arrays.asList(10, 20, 30, 40, 50); 

@Test 
public void closestOf21() { 
    assertThat(closest(21, list), is(20)); 
} 

@Test 
public void closestOf19() { 
    assertThat(closest(19, list), is(20)); 
} 

@Test 
public void closestOf20() { 
    assertThat(closest(20, list), is(20)); 
} 

Answer 2

Chắc chắn bạn có thể chỉ cần sử dụng vòng lặp for để đi qua và theo dõi sự khác biệt giữa giá trị bạn đang ở và giá trị. Nó sẽ trông sạch hơn, nhưng chậm hơn nhiều.

Xem: Finding closest match in collection of numbers

Answer 3

Tôi nghĩ rằng những gì bạn có là khoảng cách đơn giản nhất và hiệu quả nhất để làm điều đó. Tìm mục "gần nhất" trong danh sách được sắp xếp không phải là thứ thường gặp phải trong lập trình (bạn thường tìm kiếm mục lớn hơn hoặc nhỏ hơn). Vấn đề chỉ có ý nghĩa đối với các kiểu số, do đó, không phải là rất chung chung, và do đó nó sẽ là bất thường để có một chức năng thư viện cho nó.

Answer 4

Không thử nghiệm

int[] randomArray; // your array you want to find the closest 
     int theValue; // value the closest should be near to 

     for (int i = 0; i < randomArray.length; i++) { 
      int compareValue = randomArray[i]; 

      randomArray[i] -= theValue; 
     } 

     int indexOfClosest = 0; 
     for (int i = 1; i < randomArray.length; i++) { 
      int compareValue = randomArray[i]; 

      if(Math.abs(randomArray[indexOfClosest] > Math.abs(randomArray[i]){ 
       indexOfClosest = i; 
      } 
     } 

Answer 5

Tôi nghĩ rằng câu trả lời của bạn có lẽ là cách hiệu quả nhất để trả về một kết quả duy nhất.

Tuy nhiên, vấn đề với cách tiếp cận của bạn là có 0 (nếu không có danh sách), 1 hoặc 2 giải pháp khả thi. Đó là khi bạn có hai giải pháp có thể cho một chức năng mà vấn đề của bạn thực sự bắt đầu: Nếu đây không phải là câu trả lời cuối cùng, nhưng chỉ là câu trả lời đầu tiên trong một loạt các bước để xác định một hành động tối ưu và câu trả lời mà bạn không trở lại sẽ cung cấp một giải pháp tốt hơn? Điều đúng đắn nhất cần làm là xem xét cả hai câu trả lời và so sánh kết quả của việc xử lý tiếp theo chỉ ở cuối.

Hãy nghĩ về chức năng gốc hình vuông như một vấn đề tương tự về vấn đề này.

Answer 6

Để giải quyết vấn đề, tôi sẽ mở rộng Giao diện có thể so sánh bằng phương thức distanceTo. Việc thực hiện distanceTo trả về một giá trị kép đại diện cho khoảng cách dự định và tương ứng với kết quả của việc thực hiện compareTo.

Ví dụ sau minh họa ý tưởng chỉ với táo. Bạn có thể trao đổi đường kính theo trọng lượng, thể tích hoặc vị ngọt.Cái túi sẽ luôn trả lại táo 'gần' (tương tự nhất về kích thước, wight hoặc hương vị)

public interface ExtComparable<T> extends Comparable<T> { 
    public double distanceTo(T other); 
} 

public class Apple implements Comparable<Apple> { 
    private Double diameter; 

    public Apple(double diameter) { 
     this.diameter = diameter; 
    } 

    public double distanceTo(Apple o) { 
     return diameter - o.diameter; 
    } 

    public int compareTo(Apple o) { 
     return (int) Math.signum(distanceTo(o)); 
    } 
} 

public class AppleBag { 
    private List<Apple> bag = new ArrayList<Apple>(); 

    public addApples(Apple...apples){ 
     bag.addAll(Arrays.asList(apples)); 
     Collections.sort(bag); 
    } 

    public removeApples(Apple...apples){ 
     bag.removeAll(Arrays.asList(apples)); 
    } 

    public Apple getClosest(Apple apple) { 
     Apple closest = null; 
     boolean appleIsInBag = bag.contains(apple); 
     if (!appleIsInBag) { 
     bag.addApples(apple); 
     } 

     int appleIndex = bag.indexOf(apple); 
     if (appleIndex = 0) { 
     closest = bag.get(1); 
     } else if(appleIndex = bag.size()-1) { 
     closest = bag.get(bag.size()-2); 
     } else { 
     double absDistToPrev = Math.abs(apple.distanceTo(bag.get(appleIndex-1)); 
     double absDistToNext = Math.abs(apple.distanceTo(bag.get(appleIndex+1)); 
     closest = bag.get(absDistToNext < absDistToPrev ? next : previous); 
     } 

     if (!appleIsInBag) { 
     bag.removeApples(apple); 
     } 

     return closest; 
    } 
} 

Answer 7

Nếu bạn không ồ ạt lo ngại về hiệu suất (cho rằng các thiết lập được tìm kiếm hai lần), tôi nghĩ rằng sử dụng một Bộ điều hướng dẫn đến mã rõ ràng hơn:

public class Closest 
{ 
    private static NavigableSet<Integer> integers = new TreeSet<Integer>(); 

    static 
    { 
    for (int i = 0; i <= 10; i++) 
    { 
     integers.add(Integer.valueOf(i * 10)); 
    } 
    } 

    public static void main(String[] args) 
    { 
    final Integer arg = Integer.valueOf(args[0]); 
    final Integer lower = integers.lower(arg); 
    final Integer higher = integers.higher(arg); 

    final Integer closest; 
    if (lower != null) 
    { 
     if (higher != null) 
     closest = (higher - arg > arg - lower) ? lower : higher; 
     else 
     closest = lower; 
    } 
    else 
     closest = higher; 

    System.out.println("The closest Integer to " + arg + " in " + integers + " is " + closest); 
    } 
} 

Answer 8

Giải pháp của bạn có vẻ tối ưu. Nó có thể hơi nhanh hơn (mặc dù có thể ít bảo trì hơn) nếu nó sử dụng Math.min/max. Một JIT tốt có thể có nội tại mà làm cho những nhanh.

int index = Collections.binarySearch(integers, arg); 
if (index < 0) { 
    int previousDate = integers.get(Math.max(0, -index - 2)); 
    int nextDate = integers.get(Math.min(integers.size() - 1, -index - 1)); 
    closest = arg - previousDate < nextDate - arg ? previousDate : nextDate; 
} else { 
    closest = integers.get(index); 
} 

Answer 9

Một giải pháp mà không tìm kiếm nhị phân (mất lợi thế của danh sách được sắp xếp):

public int closest(int value, int[] sorted) { 
    if(value < sorted[0]) 
    return sorted[0]; 

    int i = 1; 
    for(; i < sorted.length && value > sorted[i] ; i++); 

    if(i >= sorted.length) 
    return sorted[sorted.length - 1]; 

    return Math.abs(value - sorted[i]) < Math.abs(value - sorted[i-1]) ? 
     sorted[i] : sorted[i-1]; 
}