ढूँढना एक सरणी

Question

एक सरणी पहले हम एक वांछित संख्या है कि में मौजूद है या नहीं खोजने के लिए में में निकटतम नंबर? यदि नहीं तो जावा में दिए गए वांछित नंबर पर मुझे नजदीकी संख्या कैसे मिलेगी?

Answer 1

Array.indexOf() पता लगाने के लिए wheter तत्व मौजूद है या नहीं। यदि ऐसा नहीं होता है, तो एक सरणी पर पुनरावृत्ति करें और एक वेरिएबल बनाए रखें जिसमें वांछित और i -th तत्व के बीच अंतर का पूर्ण मूल्य होता है। कम से कम पूर्ण अंतर के साथ तत्व लौटें।

कुल मिलाकर जटिलता हे (2n) है, जो आगे एक सरणी से अधिक एक एकल पुनरावृत्ति में कम किया जा सकता है (जो हे (एन) होगा) है। यद्यपि बहुत अंतर नहीं होगा।

Answer 2

एक विचार:

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

सरणी सॉर्ट किया जाता है, तो एक संशोधित द्विआधारी खोज करते हैं। असल में यदि आपको संख्या नहीं मिलती है, तो खोज के अंत में निचले बाउंड को वापस कर दें।

Answer 4

केवल बात लापता करीब के शब्दों है।

क्या आप छह के लिए देख रहे हैं क्या करते हैं और अपने सरणी दोनों चार से आठ है?

कौन सा सबसे करीब है?

Answer 5

स्यूडोकोड निकटतम पूर्णांक सूची वापस जाने के लिए।

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

"करीब" का एक और सार्वजनिक परिभाषा अंतर के वर्ग पर आधारित है। रूपरेखा, romaintaz द्वारा प्रदान के समान है, सिवाय इसके कि आप

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

गणना होगी और फिर निकटतम दूरी के (d * d) की तुलना करें।

नोटकि मैं d रूप long बजाय int अतिप्रवाह, जो भी पूर्ण-मूल्य आधारित गणना के साथ हो सकता है से बचने के लिए आपके द्वारा लिखे गए। (उदाहरण के लिए, क्या होता है जब desiredValue अधिकतम 32-बिट पर हस्ताक्षर किए मूल्य का कम से कम आधा है, और सरणी इसी परिमाण लेकिन नकारात्मक संकेत के साथ एक मान के बारे में सोचते हैं।)

अंत में, मैं विधि लिखते हैं मूल्य के बजाय, मूल्य के सूचकांक को वापस करने के लिए। इन दो मामलों में से किसी में:

• जब सरणी शून्य की लंबाई है, और
• यदि आप एक "सहिष्णुता" पैरामीटर है कि अधिकतम अंतर आप एक मैच के रूप में विचार करेंगे सीमा जोड़ने के लिए,

आप का उपयोग indexOf पर spec के समान आउट-ऑफ-बैंड मान के रूप में कर सकते हैं।

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]; 
    } 

इस तरह आप पिछले संख्या वांछित संख्या के करीब पाते हैं क्योंकि bestDistanceFoundYet स्थिर है और घ अंतिम मान अगर (घ < ...) passign याद।

यदि आप वांछित संख्या (डी कोई फर्क नहीं पड़ता) द्वारा किसी भी DISTANCE के साथ निकटतम संख्या प्राप्त करना चाहते हैं, तो आप अंतिम संभाव्य मूल्य को याद कर सकते हैं। अगर आप

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); 

परीक्षण कर सकते हैं पर यह तेजी से, भी है।

ओह - आप निकटतम नंबर खोजना चाहते थे? उस स्थिति में:

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)); 

ओह - लटका: आप कम से कम वर्ग समाधान के बाद थे?

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

कुछ बताते बातें:

1 - आप

Arrays.asList(yourIntegerArray); 

2 का उपयोग कर एक सूची में सरणी में बदल सकते हैं - एक सूची का उपयोग करना, तुम सिर्फ indexOf उपयोग कर सकते हैं()।

3 - एक परिदृश्य पर विचार करें जहां आपके पास कुछ लंबाई की सूची है, आप चाहते हैं कि नंबर 3 के करीब है, आप पहले ही पाए गए हैं कि 2 सरणी में है, और आप जानते हैं कि 3 नहीं है। अन्य नंबरों की जांच किए बिना, आप सुरक्षित रूप से निष्कर्ष निकाल सकते हैं कि 2 सबसे अच्छा है, क्योंकि यह करीब होना असंभव है। मुझे यकीन नहीं है कि indexOf() कैसे काम करता है, हालांकि, यह वास्तव में आपको गति नहीं दे सकता है।

4 - 3 पर विस्तार, मान लें कि indexOf() को किसी इंडेक्स पर मान प्राप्त करने से अधिक समय नहीं लगता है। फिर यदि आप किसी सरणी में 3 से निकटतम संख्या चाहते हैं और आपको पहले से ही 1 मिल गया है, और जांचने के लिए कई और संख्याएं हैं, तो यह जांचने के लिए तेज़ होगा कि 2 या 4 सरणी में है या नहीं।

5 - 3 और 4 पर विस्तार, मुझे लगता है कि इसे फ्लोट्स और युगल में लागू करना संभव हो सकता है, हालांकि इसकी आवश्यकता होगी कि आप चरण 1 से छोटे आकार का उपयोग करें ... गणना करना कि कितना छोटा गुंजाइश है सवाल, यद्यपि।

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

// यह काम करेंगे

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; 
}