給定一個整數數組，找出數組中第三大的值

public int thirdLargest(int[] arr){ 

     int f_l = arr[0]; 
     int s_l = arr[0]; 
     int t_l = arr[0]; 

     for(int i=1;i<arr.length;i++) 
     { 
     if (f_l < arr[i]){ 
     t_l = s_l; 
     s_l = f_l; 
     f_l = arr[i]; 
     } 
     else if (s_l < arr[i]){ 
     t_l = s_l; 
     s_l = arr[i]; 
     } 
     else if (t_l < arr[i]){ 
     t_l = arr[i]; 
     } 
     } 
    return t_l; 
}

我的代碼沒有通過一些情況，有什麼建議嗎？給定一個整數數組，找出數組中第三大的值

parameter {24,27,30,31,34,37,40,42}' , passes 

parameter {2,-1,-2,-3,-4,-5}' , fails

來源

2015-08-26 Pallavi Singh

@paul是對的但爲什麼不使用Arrays.sort（降序）然後提取第三個值？ – Arijoon

Arrays.sort將爲O（nlog（n）），或者通過列表3次刪除最大值（對於第x個最大值將爲O（3n）或O（xn）） – Arijoon

@Arijoon太昂貴：成本'O（n日誌n）'時間而不是'O（n）' – Dici

這很簡單，因爲您將所有值初始化爲arr[0]。如果所有元素都小於arr[0]，則此代碼不會更新這些值，即使第二大元素例如不是arr[0]。而是用Integer.MIN_VALUE初始化第三個/第二個/最大值的變量，並使用第一個元素（索引= 0）而不是第二個元素開始搜索。

來源

2015-08-26 21:25:11 Paul

不要忘記在'i = 0'開始for循環後做這個改變 – gla3dr

@ gla3dr謝謝，忘記了，編輯 – Paul

@Paul感謝，它的工作.. –

實際上有一個衆所周知的算法，它比你的算法更通用。它被稱爲quick-select，看起來像一個快速排序，優化使其更快（平均線性時間）：因爲我們不需要對數組進行排序，所以我們只是對包含我們正在尋找的索引的數組部分進行遞歸（在你的情況下，第三項索引2）。

這是在Java中實現：

private static final Random rd = new Random(); 

public static int kthElement(int[] arr, int k) { 
    return kthElement(arr,k,0,arr.length); 
} 

private static T kthElement(int[] arr, int k, int min, int max) { 
    if (min < max - 1) { 
     int p = pivot(arr,min,max); 
     return p == k - 1 ? arr[p]      : 
       p < k - 1 ? kthElement(arr,k,p + 1,max) : kthElement(arr,k,min,p); 
    } 
    return arr[min]; 
} 

private static int pivot(int[] arr, int min, int max) { 
    int pivot = min + rd.nextInt(max - min); 
    swap(arr,pivot,max - 1); 
    pivot = min; 
    for (int i=min ; i<max ; i++) 
     if (arr[i] < arr[max - 1]) swap(arr,i,pivot++); 
    swap(arr,max - 1,pivot);   
    return pivot; 
} 

private static void swap(int[] arr, int i, int j) { 
    int tmp = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = tmp; 
}

來源

2015-08-26 21:34:11 Dici

那麼，作爲一種替代你的工作代碼，這裏是一個解決方案，讓您使用集合做找到你的數組中的第N個整數繁重：

import java.util.Arrays; 
import java.util.Collections; 

public class ArrayNthLargest { 

    public static int getNthLargest(int[] arrayInput, int n) { 

     Integer[] sortedArray = new Integer[arrayInput.length]; 

     for (int i = 0; i < arrayInput.length; i++) { 
      sortedArray[i] = new Integer(arrayInput[i]); 
     } 

     Arrays.sort(sortedArray, Collections.reverseOrder()); 
     return (sortedArray[n - 1]); 
    } 

    public static void main(String[] args){ 
     int nth = new Integer(0); 
     int n = new Integer(3); 
     int[] testArray = {1,2,3,4,5,6,23,44,55,8,1}; 

     nth = getNthLargest(testArray, n); 
     System.out.printf("The %d sorted array value is %d", n, nth); 

    } 
}

來源

2015-08-26 21:52:11

這實際上是一個有趣的問題，我在O（n）的複雜的事情。我希望這個解決方案是命令n。我用了一個ArrayList作爲堆棧（因爲Stack對象不允許除了在具體發病率的項目（我已經廣義它）。

public int thirdLargest(int[] arr){ 
    public int N_TH = 3; // Assuming this is nth largest you want 
    public ArrayList<Integer> largest = new ArrayList<Integer>(N_TH); 

    for(int i = 0;i<N_TH;i++) 
    largest.add(0); // initialize the ArrayList 

    for(int i = 0;i<arr.length;i++) { 
    for(int j=0;j<largest.size();j++){ 
     if(arr[i] >= largest.get(j)) { 
     // Add the item at the correct index 
     // Pop the last element 
     largest.remove(largest.size()-1); 
     largest.add(j,arr[i]); 
     break; 
     } 
    } 
    } 
    return largest.get(N_TH); 
}

我們，如果你發現任何問題，它我，我可能有試圖把它放在OP的方法輸錯的一部分。

EDIT不會在此刻負數工作。您可以在arr找到最小的值，並用該值初始化largest，然後將其與還會負號

來源

2015-08-26 22:13:33 Arijoon

給定一個整數數組，找出數組中第三大的值

回答

相關問題