1

ソートを使用せずに、配列内で 2 番目に小さい数を見つけるメソッドを作成しました。配列内で 3 番目に小さい数を見つけるために同じロジックを拡張できると思ったのですが、そう簡単ではないことに気付きました。睡眠不足か何かによる..以下は、findSecondSmallest と findThirdSmallest の私のコードです..誰かが後で私のロジックの欠陥を修正できますか?

public class ArrayElementSelection{
    public static int findSecondSmallest(int[] a){
            int N = a.length;
            int min = 0;
            int secondSmallest = 0;
            for(int i=1;i<N;i++){
                if(a[i] < a[min]){
                    secondSmallest = min;
                    min = i;

                }else if(a[i] < a[secondSmallest]){
                    secondSmallest = i;
                }
            }
            return a[secondSmallest];
        }

    public static int findThirdSmallest(int[] a){
            int N = a.length;
            int min = 0;
            int secondSmallest = 0;
            int thirdSmallest = 0;
            for(int i=1;i<N;i++){
                if(a[i] < a[min]){
                    min = i;
                }else if(a[i] < a[secondSmallest]){
                    secondSmallest = i;
                }else if(a[i]< a[thirdSmallest]){
                    thirdSmallest = i;
                }
            }

            return a[thirdSmallest];
        }

    public static void main(String[] args) {
         int[] a = new int[]{4,2,3,1,5};
         System.out.println(findThirdSmallest(a));
    }
}

>> 4
4

9 に答える 9

3

よし、少し掃除しよう。配列内で 3 番目に小さい要素を探します。

    NavigableSet<Integer> min3 = new TreeSet<Integer>();
    //We keep only 3 elements in min3, as soon as the set size grows over 3
    //we remove the last element, which is the max.

    for (int x : array) {
        min3.add(x);
        if (min3.size() > 3) {
            min3.pollLast();
        } 
    }

    if (array.length >= 3) {
        Integer thirdMinimum = min3.pollLast();
        System.out.println(thirdMimimum);
    } else {
       //array must contain at least 3 elements
    }

上記のコード スニペットは、3 番目の一意の最小値を見つけます。整数のセットの代わりに、ソートされた整数のリストを保持する場合。3 番目の一意でない最小値を見つけることができます。

于 2013-07-11T18:06:04.373 に答える
2

配列内の 3 つの最小項目を検索するロジックは次のとおりです。ソース配列に 100 個の要素があるとします。3 つの要素を持つ temp という名前の新しい配列を作成し、すぐにソース配列の最初の 3 つの要素をそれに追加してから、並べ替えます (3 要素の配列を並べ替えるのは簡単です)。temp の最大要素のサイズをマークダウンし、maxTemp と呼びます。

次に、ソース配列全体を通して 4 番目の要素からループを開始します。maxTemp よりも小さい要素が見つかった場合:

1) 一時配列内でこの新しい値が収まる場所を特定し、それを入れて、それに応じて大きな値を上にシフトします。以前の maxTemp は大きすぎて認定できないため、削除します。

2) 新しい maxTemp を設定します

3) ループを続ける

完了すると、一時配列に最小の 3 つの要素が保持されます。

于 2013-07-11T17:50:18.293 に答える
2

これを行う一般的な方法があります: プライオリティ キューを使用します。

  • 最大のアイテムが最初にキューから取り出される優先キューを作成します
  • リスト内のアイテムを繰り返し処理し、それらを優先キューに追加します
  • プライオリティ キューが k アイテムを超えるたびに、アイテムをデキューする
  • 反復が終了すると、k 番目に小さいアイテムが優先キューの先頭になります

プライオリティ キューの操作にはO(log(X))時間がかかります。ここXで、 はキュー内のアイテムの数です。プライオリティ キューが を超えないためk、各操作に時間がかかりO(log(k))ます。を設定して定数を作ると、全体のプロセスにO(n log(k))時間がかかります。O(n)kk=3

于 2013-07-11T20:40:41.177 に答える
1

おそらくこれを行う最善の方法ではありませんが、最初の例がどのように機能するかを拡張するには、次のようになると思います。

public static int findThirdSmallest(int[] a){
        int N = a.length;
        int min = 0;
        int secondSmallest = 1;
        int thirdSmallest = 2;
        for(int i=1;i<N;i++){
            if(a[i] < a[min]){
                thirdSmallest = secondSmallest;
                secondSmallest = min;
                min = i;
            }
        }
        return a[thirdSmallest];
    }

配列の長さが 3 未満の場合はバグが発生しますが、それ以外の場合は機能するはずです。

編集:実際にそれを見ると、あなたのアルゴリズムは正しくありません.配列を1回だけ通過しながらn番目に小さい数を取得する方法はないと思います.単純に最小値を見つけてからもう一度通過する必要があります.最小値と比較して次の番号などを見つけます。n 番目に小さい要素を取得するためのパフォーマンスがひどいため、素朴に言いますが、仕事は完了します。

于 2013-07-11T17:50:33.317 に答える
0

私はこれが面白いと思ったので、それを解決するための小さな再帰的な方法をすぐに書きました。これは、指定された N 番目に小さい要素 (int の配列、N 番目に小さい数値、および 0 (開始参照)) を解決します。

public class Thir {
    public static void main(String[] args) {
      int[] a = new int[]{4,2,3,1,5};
      System.out.println(findNthSmallest(a,3,0));
    }

    static int findNthSmallest(int [] array, int n, int last) {
      if (n == 0)
        return last;
      int MAX = 9999;
      int pos = 0;
      int curMin = 0;
      boolean changed = false;
      for (int i = 0; i < array.length; i++)
      {
        if (changed == false && array[i] > last)
         {
          curMin = array[i];
          changed = true;
         }
        if (array[i] < curMin)
        {
          pos = i;
          curMin = array[i];
        }
      }
      array[pos] = MAX;
      return findNthSmallest(array, n-1, curMin);
    }
}
于 2013-07-11T17:58:10.810 に答える
0

時間 N * log N で X 番目に小さい要素または最大の要素を取得するには、優先キューまたは TreeSet を使用する必要があります。

基本的に TreeSet を作成し、配列をトラバースするときにアイテムをピットします。終了したら、単に TreeSet を反復処理し、イテレータの下の N 番目のアイテムを探します。

于 2013-07-11T18:00:40.017 に答える
0 
public int thirdSmallest(Int[] arr){

    for(int x = 0; x < arr.length; x++){
       for(int y = 0; y < arr.length; y++){
           if(arr[x] > arr[y]){
             int z = arr[x];
             arr[x] = arr[y];
             arr[y] = z;
           }
       }       
    }
  return arr[2]; //third smallest
}
于 2013-07-11T18:07:03.560 に答える