java - 配列で 2 番目に高い値を見つける

Question

配列に10個の整数値が含まれています。次に、2 番目に大きい数値を調べたいと思います。Java API は使用しないでください。この質問は、あるインタビュアーから私に聞かれました。彼はロジックを望んでいます。そして彼の要件は、要素全体をトラバースしてはならないということです。トラバースせずに結果を達成できる方法はありますか? 走査とは、配列内のすべての要素を通過することを意味します。ずっと考えていたのですが、とうとう諦めました。誰かが説明できるなら、それはいいでしょう。また、並べ替えについても尋ねました。彼は配列をソートしたくありません。

Answer 1

いいえ、それはまったく不可能です。すべてのデータを見ないと、2 番目に高い値を知ることはできません。

もちろん、すべてのデータを並べ替える必要はありません。これは、インタビュアーが意図したことかもしれませんが、すべての要素を少なくとも 1 回は確認する必要があります。どの要素も結果を変える可能性があるので、検討する必要があります。

Answer 2

それぞれの要素を一度でも見なければ答えはわかりません。ただし、それが問題でない場合は、二分探索木を使用できます。

コンピューター サイエンスでは、二分探索木 (BST) は、順序付きまたは並べ替えられた二分木と呼ばれることもあり、次のプロパティを持つノード ベースの二分木データ構造です。[1]

ノードの左側のサブツリーには、ノードのキーより小さいキーを持つノードのみが含まれます。ノードの右側のサブツリーには、ノードのキー以上のキーを持つノードのみが含まれます。左と右の部分木は両方とも二分探索木でなければなりません。
ソース: http://en.wikipedia.org/wiki/Binary_search_tree

---

2 番目に大きい要素をどのように見つけますか?

BST がどのように形成されるかから、最大の要素が一番右の要素であることがわかります (ルート ノードから始めて、行く場所がなくなるまで右の子を取ります)。

---

では、2 番目に大きいものを特定するにはどうすればよいでしょうか。
まあ、これは最も効率的なアプローチではないかもしれませんが、場合によって分けてみましょう:

1. 最大のノードはツリー ルートであり、子はありません - ツリーにはノードが 1 つしかないため、2 番目に大きい要素はありません

2. 最大のノードはツリー ルートです (右の子はありません) - 2 番目に大きい要素は、左のサブツリーの最大の要素です

3. 最大の要素はツリーのルートではなく、葉ではありません (左の子があります) - 2 番目に大きい要素は彼の左の子です

4. 最大の要素はツリーのルートではなく、葉です (子はありません) - 2 番目に大きい要素はその親です

パターンと単純なアルゴリズムを今すぐ理解できると確信しています:D

Answer 3

これが答えられたことは知っていますが、私はこのようなことを考えていました。

    double maxVal = array[0];
    for (int i=1; i < array.length; i++) {
        if (array[i] > maxVal) {
            maxVal = array[i];
        }
    }

技術的には、最初の値を最大値に割り当てるため、配列全体ではなく n-1 の長さをトラバースしています。他にも方法があると思いますが、これはインタビュアーが何を望んでいるのかについてのようです.

Answer 4

ロジックは非常に単純です。これはすでに 1 つの for ループに実装しています。

私のプログラムを差し上げます。アルゴリズムが必要な場合は、それも提供できます。

public static void main(String[] args) {

    int[] arr={0,12,74,56,2,63,45};
    int f1=1,f2=0,temp=0;
    int num=0;

    for(int i=0;i<arr.length;i++){
        num=arr[i];
        if(f1<num)
        {
            temp=f1;
            f1=num;
            num=temp;
        }
        if(f2<num)
        {
            temp=f2;
            f2=num;
            num=temp;
        }
    }
    System.out.println("First Highest "+f1+" Second Highest "+f2+" Third "+num);

}