題目?jī)?nèi)容

題目:一個(gè)數(shù)組中除了兩個(gè)數(shù)字之外,其余數(shù)字均出現(xiàn)了兩次,如{1, 2, 3, 4, 1, 2, 5, 5, 4, 7}.查找這兩個(gè)只出現(xiàn)一次的數(shù)字,要求時(shí)間復(fù)雜度為o（n）,空間復(fù)雜度為o（1）.

解法

• 基礎(chǔ)知識(shí)

與（&）:全1為1,有0則0.    0&0=0; 0&1=1;1&1=1;

或（|）:有1則1,全0則0.    0|0=0; 0|1=1; 1|1=1;

異或（^）:相同為0,不同為1. 1^1=0; 0^0=0; 0^1=1;

• 思路如下：

1. 將數(shù)組里全部數(shù)據(jù)異或一遍,由于相同數(shù)字異或結(jié)果為0,則這樣可以消除所有重復(fù)的數(shù)字,結(jié)果與兩個(gè)單次數(shù)字異或后的結(jié)果相同
2. 因?yàn)閮烧呤遣煌臄?shù)字,結(jié)果一定有一位為1.這說(shuō)明在該位上這兩個(gè)單數(shù)一個(gè)為0一個(gè)為1.由此我們將數(shù)組分成兩部分,一部分為該位為0,另一部分為1,再分別對(duì)兩組異或最終得到的兩個(gè)數(shù)值就是單次出現(xiàn)的兩個(gè)數(shù)字

• 解題步奏

1. 全組異或
2. 異或結(jié)果取出第一位不為0的位數(shù)
3. 將數(shù)組數(shù)據(jù)根據(jù)改位數(shù)是否為零分開(kāi)異或,結(jié)果則為兩個(gè)單次數(shù)字

代碼如下

Talk is cheap, show you my code!

/**
 * Created by IDEA.
 * User: mc
 * Date: 19/2/13
 * Time: 上午9:19
 */
public class TowSingleNum
{
    public static void main(String[] args)
    {
        int[] num = {1, 2, 3, 4, 1, 2, 5, 5, 4, 7};
        execute(num);
    }

    /**
     * 獲取異或結(jié)果
     *
     * @param num
     * @return
     */
    private static int getSum(int[] num)
    {
        int sum = 0;
        for (int item : num) {
            sum ^= item;
        }
        return sum;
    }

    /**
     * 執(zhí)行入口
     *
     * @param num
     */
    public static void execute(int[] num)
    {
        int sum = getSum(num);
        int index = getIndex(sum);
        int num1 = 0, num2 = 0;
        for (int item : num) {
            if (judge(item, index)) {
                num1 ^= item;
            } else {
                num2 ^= item;
            }
        }
        System.out.printf("%d, %d", num1, num2);
    }

    /**
     * 劃分?jǐn)?shù)組
     *
     * @param num
     * @param index
     * @return
     */
    private static boolean judge(int num, int index)
    {
        return ((num >> index) & 1) == 0;
    }

    /**
     * 獲取第一個(gè)不同的位數(shù)
     *
     * @param sum
     * @return
     */
    private static int getIndex(int sum)
    {
        int index = 0;
        while ((1 & sum) == 0) {
            sum = sum >> 1;
            index++;
        }
        return index;
    }
}

寫(xiě)在最后的話(huà)

小菜雞最近想換工作,杭州有沒(méi)有需要菜鳥(niǎo)后端的(php/java),薪資要求14k+,java(沒(méi)有開(kāi)發(fā)經(jīng)驗(yàn))可以稍低一些.微信號(hào)bGlueXlhbmc5Mg==