2013-07-12 13 views
8

में n अधिकतम के सूचकांकों जाओ मैं मैं सूचकांक (अनुक्रमित) पांच अधिकतम तत्वों की कैसे मिल सकता है आकार 1000 की एक सरणी है?जावा सरणी

सेटअप कोड और मेरे प्रयास के साथ एक उदाहरण नीचे दिखाया गया है:

Random rand = new Random(); 
int[] myArray = new int[1000]; 
int[] maxIndices = new int[5]; 
int[] maxValues = new int[5]; 

for (int i = 0; i < myArray.length; i++) { 
    myArray[i] = rand.nextInt(); 
} 

for (int i = 0; i < 5; i++) { 
    maxIndices[i] = i; 
    maxValues[i] = myArray[i]; 
} 

for (int i = 0; i < maxIndices.length; i++) { 
    for (int j = 0; j < myArray.length; j++) { 
    if (myArray[j] > maxValues[i]) { 
     maxIndices[i] = j; 
     maxValues[i] = myArray[j]; 
    } 
    } 
} 

for (int i = 0; i < maxIndices.length; i++) { 
    System.out.println("Index: " + maxIndices[i]); 
} 

मैं जानता हूँ कि समस्या यह है कि यह लगातार सभी अधिकतम तत्वों को उच्चतम अधिकतम मान निर्दिष्ट किया जाता है। मुझे यकीन है कि इसका समाधान कैसे करें क्योंकि मुझे myArray के मानों और सूचकांक को संरक्षित करना है। क्योंकि मैं सूचकांक के संरक्षण की जरूरत

मैं छँटाई नहीं लगता कि एक विकल्प है। असल में, यह इंडेक्स है जो मुझे विशेष रूप से चाहिए।

+0

ऐसा लगता है कि आप जब आप पाते हैं अद्यतन करने के लिए कैसे पर पुनर्विचार करने की जरूरत है लग रहा है शीर्ष 5 में एक नया तत्व 5. –

+0

[इस चर्चा] में कुछ इंडेक्स-संरक्षित दृष्टिकोण हैं (http://stackoverflow.com/questions/951848/java-array-sort-quick-way-to-get-a- सॉर्ट-सूची-ऑफ-इंडेक्स-ऑफ-ए-सरणी? rq = 1) –

+0

(स्पष्ट होने के लिए, आपका दृष्टिकोण पहले से ही बहुत करीब है; आपको केवल उस तीसरे लूप को फिर से काम करने की आवश्यकता है।) –

उत्तर

7

सॉर्टिंग अतिरिक्त मेमोरी की कीमत पर एक विकल्प है। निम्नलिखित एल्गोरिदम पर विचार करें।

1. Allocate additional array and copy into - O(n) 
2. Sort additional array - O(n lg n) 
3. Lop off the top k elements (in this case 5) - O(n), since k could be up to n 
4. Iterate over the original array - O(n) 
    4.a search the top k elements for to see if they contain the current element - O(lg n) 

तो यह चरण 4 है (एन * एलजी एन), बस इस तरह की तरह। संपूर्ण एल्गोरिदम एन एलजी एन है, और कोड के लिए बहुत आसान है।

यहां एक त्वरित और गंदा उदाहरण है। इसमें बग हो सकते हैं, और स्पष्ट रूप से शून्य जांच और जैसे खेल में आते हैं।

आयात java.util.Arrays;

class ArrayTest { 

    public static void main(String[] args) { 
     int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10}; 
     int[] indexes = indexesOfTopElements(arr,3); 
     for(int i = 0; i < indexes.length; i++) { 
      int index = indexes[i]; 
      System.out.println(index + " " + arr[index]); 
     } 
    } 

    static int[] indexesOfTopElements(int[] orig, int nummax) { 
     int[] copy = Arrays.copyOf(orig,orig.length); 
     Arrays.sort(copy); 
     int[] honey = Arrays.copyOfRange(copy,copy.length - nummax, copy.length); 
     int[] result = new int[nummax]; 
     int resultPos = 0; 
     for(int i = 0; i < orig.length; i++) { 
      int onTrial = orig[i]; 
      int index = Arrays.binarySearch(honey,onTrial); 
      if(index < 0) continue; 
      result[resultPos++] = i; 
     } 
     return result; 
    } 

} 

अन्य ऑपरेशन आप इस ऑपरेशन के ओवरहेड को कम करने के लिए कर सकते हैं। उदाहरण के लिए सॉर्ट करने के बजाए, आप एक कतार का उपयोग करने का विकल्प चुन सकते हैं जो कि सबसे बड़ा ट्रैक करता है 5. int एस होने के कारण वे शायद संग्रह में जोड़े जाने के लिए बॉक्स किए जाने चाहिए (जब तक कि आप अपना खुद का लुढ़का नहीं लेते) जो काफी हद तक ओवरहेड में जोड़ता है।

+0

@TheNewIdiot - सही उपयोग 'lg'' log' नहीं है। और 4. ए 5 जैसा नहीं है, क्योंकि यह एक अलग कदम नहीं है - यह पुनरावृत्ति के दौरान होता है। – corsiKa

+0

वे दोनों एक ही बात का मतलब है ... –

+0

@Hunter प्रकार। 'एलजी' का अर्थ है 'लॉग बेस 2'। जब बड़े 'ओ' नोटेशन में, वे एक दूसरे के साथ घनत्व करते हैं क्योंकि वे एक ही क्रम में हैं, यह सही है। हालांकि, अगर उस परिवर्तन की समीक्षा की गई तो इसे "बहुत मामूली" के रूप में खारिज कर दिया गया था, और 4. ए से 5 के परिवर्तन को "गलत" के रूप में खारिज कर दिया जाएगा। – corsiKa

0

Arrays.sort (myArray), फिर अंतिम 5 तत्व लें।

यदि आप मूल ऑर्डर को संरक्षित करना चाहते हैं तो एक प्रतिलिपि सॉर्ट करें।

आप सूचकांकों चाहते हैं, तो एक त्वरित और गंदे समाधान के रूप में वहाँ अजगर या कुछ अन्य भाषाओं में होगा नहीं है। आप सॉर्ट और स्कैन करते हैं, लेकिन वह बदसूरत है।

या आप objecty जा सकते हैं - यह जावा सब के बाद है। एक ArrayMaxFilter ऑब्जेक्ट बनाएं। इसमें एक निजी श्रेणी एरेलेमेंट होगा, जिसमें एक इंडेक्स और एक वैल्यू होगा और उसके पास मूल्य से प्राकृतिक ऑर्डर होगा। इसमें एक विधि होगी जो कि इंक, इंडेक्स और वैल्यू की एक जोड़ी लेती है, उनमें से एक ऐरेलेमेंट बनाता है, और उन्हें लंबाई 5 की प्राथमिकता कतार में छोड़ देता है (या फिर भी आप जो खोजना चाहते हैं)। सरणी से प्रत्येक अनुक्रमणिका/मूल्य जोड़ी जमा करें, फिर कतार में शेष मानों की रिपोर्ट करें। (हाँ, एक प्राथमिकता कतार पारंपरिक रूप से सबसे कम मूल्यों रहता है, लेकिन आप अपने कार्यान्वयन में इस फ्लिप कर सकते हैं)

+1

ओपी मूल सरणी में इंडेक्स को संरक्षित करना चाहता है। – corsiKa

0

मेरे त्वरित और थोड़ा "बॉक्स के बाहर लगता है कि" विचार EvictingQueue कि 5 के एक अधिकतम रखती उपयोग करने के लिए किया जाएगा तत्वों। आपको इसे अपने सरणी के पहले पांच तत्वों से पहले भरना होगा (इसे आरोही क्रम में करें, इसलिए आपके द्वारा जोड़ा गया पहला तत्व पांच से सबसे कम है)।

से आप सरणी के माध्यम से पुनरावृति और कतार में एक नया तत्व जोड़ जब भी वर्तमान मान कतार में सबसे कम मूल्य से अधिक है करने के लिए है। इंडेक्स को याद रखने के लिए, एक रैपर ऑब्जेक्ट बनाएं (एक मान/अनुक्रमणिका जोड़ी)।

पूरे सरणी के माध्यम से दोहराने के बाद, आप कतार में अपनी पांच अधिकतम मूल्य/सूचकांक जोड़े (घटते क्रम में) है।

यह एक ओ (एन) समाधान है।

+0

ऐसा ही है कि मेरा उत्तर xD – nachokk

0

मेरा समाधान यहां है। एक कक्षा बनाएं कि जोड़े के एक मूल्य के साथ एक indice:

public class IndiceValuePair{ 
    private int indice; 
    private int value; 

    public IndiceValuePair(int ind, int val){ 
     indice = ind; 
     value = val; 
    } 
    public int getIndice(){ 
     return indice; 
    } 
    public int getValue(){ 
     return value; 
    } 
} 

और फिर अपने मुख्य विधि में इस वर्ग का उपयोग करें:

Here are the indices and their values: 
0: 13 
1: 71 
2: 45 
3: 38 
4: 43 
5: 9 
6: 4 
7: 5 
8: 59 
9: 60 

5 Max indices and their values 
1: 71 
9: 60 
8: 59 
2: 45 
4: 43 

: एक रन से

public static void main(String[] args){ 
    Random rand = new Random(); 
    int[] myArray = new int[10]; 
    IndiceValuePair[] pairs = new IndiceValuePair[5]; 
    System.out.println("Here are the indices and their values:"); 
    for(int i = 0; i < myArray.length; i++) { 
     myArray[i] = rand.nextInt(100); 
     System.out.println(i+ ": " + myArray[i]); 
     for(int j = 0; j < pairs.length; j++){ 
      //for the first five entries 
      if(pairs[j] == null){ 
       pairs[j] = new IndiceValuePair(i, myArray[i]); 
       break; 
      } 
      else if(pairs[j].getValue() < myArray[i]){ 
       //inserts the new pair into its correct spot 
       for(int k = 4; k > j; k--){ 
        pairs[k] = pairs [k-1]; 
       } 
       pairs[j] = new IndiceValuePair(i, myArray[i]); 
       break; 
      } 
     } 
    } 
    System.out.println("\n5 Max indices and their values"); 
    for(int i = 0; i < pairs.length; i++){ 
     System.out.println(pairs[i].getIndice() + ": " + pairs[i].getValue()); 
    } 
} 

और उदाहरण उत्पादन उदाहरण के लिए मैंने केवल 0 और 99 के बीच मूल्य के साथ दस इंट उत्पन्न किए हैं ताकि मैं देख सकूं कि यह काम करता है। आप किसी भी आकार के 1000 मानों को फिट करने के लिए इसे आसानी से बदल सकते हैं। इसके अलावा, लूप के लिए 3 अलग चलाने के बजाए, मैंने यह देखने के लिए जांच की कि क्या मैं myArray में जोड़ने के बाद सबसे नया मूल्य जोड़ता हूं। यह एक रन दे दो और देखो अगर यह जवाब देने में देर के लिए आप

3

एक सा काम करता है, आप भी इस समारोह है कि मैंने लिखा इस्तेमाल कर सकते हैं:

/** 
    * Return the indexes correspond to the top-k largest in an array. 
    */ 
public static int[] maxKIndex(double[] array, int top_k) { 
    double[] max = new double[top_k]; 
    int[] maxIndex = new int[top_k]; 
    Arrays.fill(max, Double.NEGATIVE_INFINITY); 
    Arrays.fill(maxIndex, -1); 

    top: for(int i = 0; i < array.length; i++) { 
     for(int j = 0; j < top_k; j++) { 
      if(array[i] > max[j]) { 
       for(int x = top_k - 1; x > j; x--) { 
        maxIndex[x] = maxIndex[x-1]; max[x] = max[x-1]; 
       } 
       maxIndex[j] = i; max[j] = array[i]; 
       continue top; 
      } 
     } 
    } 
    return maxIndex; 
} 
+0

जारी रखने से बचने के लिए कुछ स्थितियों का उपयोग करने का प्रयास करें: http://programmers.stackexchange.com/questions/58237/are-break-and-continue-bad-programming-practices –

संबंधित मुद्दे