Tìm số gần nhất trong một mảng

Question

Trong một mảng đầu tiên, chúng ta phải tìm số liệu mong muốn có tồn tại trong đó hay không? Nếu không thì làm thế nào tôi sẽ tìm số gần hơn với số mong muốn nhất định trong Java?

Answer 1

Array.indexOf() để tìm nguyên tố wheter tồn tại hay không. Nếu không, lặp lại trên một mảng và duy trì một biến chứa giá trị tuyệt đối của sự khác biệt giữa phần tử mong muốn và i -th. Trả về phần tử với sự khác biệt tuyệt đối ít nhất.

Nhìn chung phức tạp là O (2n), có thể được tiếp tục giảm đến một sự lặp lại duy nhất trên một mảng (mà muốn được O (n)). Tuy nhiên, sẽ không tạo ra nhiều khác biệt.

Answer 2

Một ý tưởng:

int nearest = -1; 
int bestDistanceFoundYet = Integer.MAX_INTEGER; 
// We iterate on the array... 
for (int i = 0; i < array.length; i++) { 
    // if we found the desired number, we return it. 
    if (array[i] == desiredNumber) { 
    return array[i]; 
    } else { 
    // else, we consider the difference between the desired number and the current number in the array. 
    int d = Math.abs(desiredNumber - array[i]); 
    if (d < bestDistanceFoundYet) { 
     // For the moment, this value is the nearest to the desired number... 
     bestDistanceFoundYet = d; // Assign new best distance... 
     nearest = array[i]; 
    } 
    } 
} 
return nearest; 

Answer 3

Nếu mảng được sắp xếp, sau đó thực hiện tìm kiếm nhị phân thay đổi. Về cơ bản nếu bạn không tìm thấy số, sau đó vào cuối tìm kiếm trả về giới hạn dưới.

Answer 4

Điều duy nhất còn thiếu là ngữ nghĩa gần hơn.

Bạn sẽ làm gì nếu bạn đang tìm kiếm sáu và mảng của bạn có cả bốn và tám?

Cái nào gần nhất?

Answer 5

Mã giả để trả về danh sách các số nguyên gần nhất.

myList = new ArrayList();   

if(array.length==0) return myList; 

myList.add(array[0]); 

int closestDifference = abs(array[0]-numberToFind); 

for (int i = 1; i < array.length; i++) { 

int currentDifference= abs(array[i]-numberToFind); 

    if (currentDifference < closestDifference) { 

    myList.clear(); 

    myList.add(array[i]); 

     closestDifference = currentDifference; 

    } else { 

    if(currentDifference==closestDifference) { 

     if(myList.get(0) !=array[i]) && (myList.size() < 2) { 

      myList.add(array[i]); 

     } 
      } 

     } 

} 

return myList; 

Answer 6

Định nghĩa chung khác về "gần hơn" được dựa trên bình phương của sự khác biệt. Đường viền tương tự như đường viền được cung cấp bởi romaintaz, ngoại trừ việc bạn muốn tính

long d = ((long)desiredNumber - array[i]); 

và sau đó so sánh (d * d) với khoảng cách gần nhất.

Notemà tôi đã gõ d như long hơn int để tránh tràn, có thể xảy ra ngay cả với các tính tuyệt đối có giá trị dựa trên. (Ví dụ: suy nghĩ về những gì sẽ xảy ra khi desiredValue ít nhất là một nửa giá trị đã ký tối đa 32 bit và mảng chứa giá trị có độ lớn tương ứng nhưng dấu âm.)

Cuối cùng, tôi sẽ viết phương thức để trả về chỉ mục của giá trị được đặt, thay vì giá trị của chính nó. Trong một trong hai trường hợp sau đây:

• khi mảng có chiều dài bằng không, và
• nếu bạn thêm một "khoan dung" tham số đó tiếp giáp với chênh lệch tối đa mà bạn sẽ xem xét như một trận đấu,

bạn có thể sử dụng -1 làm giá trị ngoài băng tương tự với thông số kỹ thuật trên indexOf.

Answer 7

int d = Math.abs(desiredNumber - array[i]); 
    if (d < bestDistanceFoundYet) { 
     // For the moment, this value is the nearest to the desired number... 
     nearest = array[i]; 
    } 

Bằng cách này bạn tìm thấy những số cuối cùng gần gũi hơn với số lượng mong muốn vì bestDistanceFoundYet là hằng số và d ghi nhớ giá trị cuối cùng passign nếu (d < ...).

Nếu bạn muốn tìm số gần hơn VỚI bất kỳ DISTANCE nào theo số mong muốn (d không phải là vấn đề), bạn có thể ghi nhớ giá trị possibile cuối cùng. Tại nếu bạn có thể kiểm tra

if(d<last_d_memorized){ //the actual distance is shorter than the previous 
    // For the moment, this value is the nearest to the desired number... 
      nearest = array[i]; 
    d_last_memorized=d;//is the actual shortest found delta 
} 

Answer 8

int[] somenumbers = getAnArrayOfSomenumbers(); 
int numbertoLookFor = getTheNumberToLookFor(); 

boolean arrayContainsNumber = 
    new HashSet(Arrays.asList(somenumbers)) 
     .contains(numbertoLookfor); 

Đó là nhanh chóng, quá.

Ồ - bạn muốn tìm số gần nhất? Trong trường hợp đó:

int[] somenumbers = getAnArrayOfSomenumbers(); 
int numbertoLookFor = getTheNumberToLookFor(); 

ArrayList<Integer> l = new ArrayList<Integer>(
    Arrays.asList(somenumbers) 
); 
Collections.sort(l); 
while(l.size()>1) { 
    if(numbertoolookfor <= l.get((l.size()/2)-1)) { 
    l = l.subList(0, l.size()/2); 
    } 
    else { 
    l = l.subList(l.size()/2, l.size); 
    } 
} 

System.out.println("nearest number is" + l.get(0)); 

Oh - gác máy: bạn đã theo một giải pháp bình phương nhỏ nhất?

Collections.sort(l, new Comparator<Integer>(){ 
    public int compare(Integer o1, Integer o2) { 
    return (o1-numbertoLookFor)*(o1-numbertoLookFor) - 
      (o2-numbertoLookFor)*(o2-numbertoLookFor); 
    }}); 

System.out.println("nearest number is" + l.get(0)); 

Answer 9

Một số điều cần chỉ ra:

1 - Bạn có thể chuyển đổi mảng vào một danh sách sử dụng

Arrays.asList(yourIntegerArray); 

2 - Sử dụng một danh sách, bạn chỉ có thể sử dụng indexOf().

3 - Hãy xem xét trường hợp bạn có danh sách độ dài, bạn muốn số gần nhất là 3, bạn đã thấy rằng 2 nằm trong mảng và bạn biết rằng 3 không phải là. Nếu không kiểm tra các số khác, bạn có thể kết luận một cách an toàn rằng 2 là tốt nhất, bởi vì nó không thể gần hơn. Tôi không chắc làm thế nào indexOf() hoạt động, tuy nhiên, do đó, điều này có thể không thực sự tăng tốc độ bạn lên.

4 - Mở rộng trên 3, giả sử indexOf() không mất nhiều thời gian hơn nhận giá trị tại chỉ mục. Sau đó, nếu bạn muốn số gần nhất với 3 trong một mảng và bạn đã tìm thấy 1 và có nhiều số khác để kiểm tra thì sẽ nhanh hơn nếu chỉ kiểm tra xem 2 hoặc 4 có nằm trong mảng hay không.

5 - Mở rộng trên 3 và 4, tôi nghĩ có thể áp dụng điều này cho phao và tăng gấp đôi, mặc dù nó sẽ yêu cầu bạn sử dụng kích thước bước nhỏ hơn 1 ... câu hỏi, mặc dù.

Answer 10

// paulmurray's answer to your question is really the best : 

// The least square solution is way more elegant, 
// here is a test code where numbertoLookFor 
// is zero, if you want to try ... 

import java.util.* ; 

public class main { 
    public static void main(String[] args) 
    { 
     int[] somenumbers = {-2,3,6,1,5,5,-1} ; 
     ArrayList<Integer> l = new ArrayList<Integer>(10) ; 
     for(int i=0 ; i<somenumbers.length ; i++) 
     { 
      l.add(somenumbers[i]) ; 
     } 
     Collections.sort(l, 
       new java.util.Comparator<Integer>() 
       { 
        public int compare(Integer n1, Integer n2) 
        { 
         return n1*n1 - n2*n2 ; 
        } 
       } 
     ) ; 
     Integer first = l.get(0) ; 
     System.out.println("nearest number is " + first) ; 
    } 
} 

Answer 11

// Điều này sẽ làm việc

public int nearest(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; 
}