JAva面接アルゴリズム問題(1)

引用する
このブログの核心はjavaの優れた演算子操作を紹介し、いくつかの独特な思考を含む.面接の過程で、これらの問題に直面する可能性もあります.筆者はアリババの電話面接の過程でこのような問題に遭遇した.みんなに分かち合います.
タイトル
整形(int)配列のセットが与えられ、この配列には1つの数字だけが単独であり、他の数字は2回以上現れた.もちろん出現回数はすべて統一され,全部で2回出現するか,全部で何度も出現する.
分析1
最も簡単な方法で、最も考えやすいのは、まずこの配列を並べ替えて、それから隣接して比較して、一度しか現れない数字を見つけることです.言い換えれば、前の数と後ろの数が異なる数字が存在すると、一度しか現れません.この処理方法は,並べ替えの方法に重点を置き,並べ替えの時間的複雑さが最終的な結果に直接影響する.従来のブログでは、ソートにおける高速ソートとスタックソートが時間的複雑度が最も低いソート方式であると述べていますが、高速ソートを用いてこの問題を解決することができます.しかし、これは本編のブログの核心ではなく、必要な学生は自分でソート方法を探したり、ブロガーの以前のブログで探したりすることができます.
実装コード1

package com.brickworkers;

import java.util.Arrays;
/**
 * 
 * @author Brickworker
 * Date:2017 6 28   2:25:55 
 *    Example.java   ：                  
 * Copyright (c) 2017, brcikworker All Rights Reserved.
 */
public class Example {

    public static int getSingle(int[] a){
        //         
        //          ，      Arrays      ，                   
        Arrays.sort(a);
        for (int i = 1; i < a.length - 1; i++) {//   1  ，      
            if(a[i] != a[i-1]){//             
                //     ，            
                if(a[i] != a[i+1]){
                    //                  
                    return a[i];
                }
            }
        }
        return Integer.MIN_VALUE;//       

    }

    public static void main(String[] args) {
        //           2 
        int[] a = {1,2,3,4,5,6,7,8,9,1,2,4,5,6,7,8,9};
        System.out.println("       " + getSingle(a));
        //       ，     3 
        int[] b = {1,2,3,4,5,6,7,8,9,1,2,4,5,6,7,8,9,1,2,4,5,6,7,8,9};
        System.out.println("       " + getSingle(b));
    }


}
//    ：
//       3
//       3

このアルゴリズムの処理方法は、あなたが選択したソートアルゴリズムの性能に直接影響されます.しかし、それは通用して、あなたがどんなに大きな倍数の出現回数の配列であっても、よく解決することができます.
分析2
異或(^)操作の機能を知らない仲間もいるかもしれませんが、異或操作具は交換律と結合律を満たしています.つまり、異或操作は以下の式を満たしています.X^X=0^X=X、つまり、同じ数字が偶数であれば、それは相殺されます.私たちは配列を遍歴して、彼らを一度異や操作することができて、それでは最後の結果はその存在の数です.しかし,配列にのみ適用して偶次が現れるという致命的な欠陥がある.しかし,利点は否めず,配列を1回巡るだけでよい.
実装コード2

package com.brickworkers;

/**
 * 
 * @author Brickworker
 * Date:2017 6 28   2:25:55 
 *    Example.java   ：              ，               
 * Copyright (c) 2017, brcikworker All Rights Reserved.
 */
public class Example {

    public static int getSingle(int[] a){
        //      
        int result = a[0];
        for (int i = 1; i < a.length; i++) {
            result ^= a[i];
        }
        return result;

    }

    public static void main(String[] args) {
        //           2 
        int[] a = {1,2,3,4,5,6,7,8,9,1,2,4,5,6,7,8,9};
        System.out.println("       " + getSingle(a));

    }


}
//    ：
//       3
//

コードは簡単で洗練されており、非常に優れた解決策です.
分析3
2つ目の方法は上手ですが、偶次が硬伤になったことを探すしかありません.倍数が奇次ならどうすればいいのだろうか.1つ目の方法ではアルゴリズムの時間的複雑さが高いように見えます.実際には、より良い、より一般的な解決策もあります.
1つの値が存在することを考えてみてください.この値が何度も現れると、そのバイナリの各ビット数の1加算は、必ず回数で除かれます.例えば、{3,3,3,2,1,1,1,1}がバイナリに変換されると、11,11,10,01,01,01は、2を除いたバイナリ10を発見することができます.残りの6つの数字、低位と高位の加算はそれぞれ3と6です.すべて3で除去することができます.では、この2を探すには、(1+1+1+1)/3=0高位:(1+1+1)/3=1 PS:そのうちの1つが2のバイナリである場合、この出現1回の数字は高位+低位=10である.
実装コード3

package com.brickworkers;

/**
 * 
 * @author Brickworker
 * Date:2017 6 28   2:25:55 
 *    Example.java   ：              
 * Copyright (c) 2017, brcikworker All Rights Reserved.
 */
public class Example {

    public static int getSingle(int[] a, int times) {
        //       ，             
        int[] count = new int[32]; // int   4   32 
        //     ，            
        for (int i = 0; i < a.length; i++) {
            //             
            for (int j = 0; j < 32; j++) {
                count[j] += ((a[i] >> j) & 1);//    a[i]           。&  ：1&1=1；1&0=0
            }
        }
        int result=0;//       
        //        ，                 ，           

        for(int i = 0; i < 32; i++){
            if(count[i] % times !=0){
                result += (1<//        ，       1     
            }
        }
        return result;
    }

    public static void main(String[] args) {
        //           3 
        int[] a = {1,2,3,4,5,6,7,8,9,1,2,4,5,6,7,8,9,1,2,4,5,6,7,8,9};
        System.out.println("       " + getSingle(a, 3));

    }


}

//    ：
//       3
//
//

まとめ
面接の過程で、普通の人は第一の方法しか考えられません.後ろの2種類が思いもよらなかったのは、存在を知らないことが多い:1 X^X=0;0^X=X,②各ビット値を加算すると必ず回数で割り切れるという法則.大神を除いて、どうせ筆者は当時思いもよらなかった.
あなたの役に立つことを望みます