本文首發(fā)于我的個(gè)人博客：尾尾部落

題目描述

一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了偶數(shù)次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。

解題思路

法一：大家都能想到的HashMap法
法二：異或法

任何一個(gè)數(shù)字異或它自己都等于0。

如果數(shù)組中只一個(gè)數(shù)字是只出現(xiàn)一次的，其他數(shù)字都是成雙成對(duì)出現(xiàn)的，那么我們從頭到尾依次異或數(shù)組中的每個(gè)數(shù)字，最終的結(jié)果剛好就是那個(gè)只出現(xiàn)一次的數(shù)字，因?yàn)槟切┏蓪?duì)出現(xiàn)兩次的數(shù)字全部在異或中抵消了。

那么回到我們的題目，因?yàn)橛袃蓚€(gè)只出現(xiàn)一次的數(shù)字，所以我們可以試著把原數(shù)組分成兩個(gè)子數(shù)組，使得每個(gè)數(shù)組包含一個(gè)只出現(xiàn)一次的數(shù)字，而其他數(shù)字都成對(duì)出現(xiàn)兩次。如果這樣拆分成兩個(gè)數(shù)組，那么我們就可以按照之前的辦法分別對(duì)兩個(gè)數(shù)組進(jìn)行異或運(yùn)算找出兩個(gè)只出現(xiàn)一次的數(shù)字。

問題來了，如何進(jìn)行分組呢？
我們還是從頭到尾依次異或數(shù)組中的每個(gè)數(shù)字，那么最終得到的結(jié)果就是兩個(gè)只出現(xiàn)一次的數(shù)字異或的結(jié)果。由于這兩個(gè)數(shù)字不一樣，所以異或的結(jié)果至少有一位為1，我們在結(jié)果數(shù)字中找到第一個(gè)為1的位置，記為index位，現(xiàn)在我們以第index位是不是1為標(biāo)準(zhǔn)把原數(shù)組拆分成兩個(gè)子數(shù)組，第一個(gè)子數(shù)組中的數(shù)組第index位都為1，第二個(gè)子數(shù)組中的數(shù)組第index位都為0，那么只出現(xiàn)一次的數(shù)字將被分配到兩個(gè)子數(shù)組中去，于是每個(gè)子數(shù)組中只包含一個(gè)出現(xiàn)一次的數(shù)字，而其他數(shù)字都出現(xiàn)兩次。這樣我們就可以用之前的方法找到數(shù)組中只出現(xiàn)一次的數(shù)字了。

參考代碼

法一：HashMap

import java.util.HashMap; public class Solution {public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>();for(int i = 0; i < array.length; i++){if(temp.containsKey(array[i]))temp.remove(array[i]);elsetemp.put(array[i], 1);}int [] a = new int [array.length];int i = 0;for(Integer k: temp.keySet()){a[i] = k;i++;}num1[0] = a[0];num2[0] = a[1];} }

法二：異或法

public class Solution {public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {num1[0] = 0;num2[0] = 0;if(array.length == 0)return;int num = 0;for(int i = 0; i < array.length; i++){num ^= array[i];}int index = 0;while((num & 1) == 0 && index < 8){num = num >> 1;index ++;}for(int i = 0; i < array.length; i++){if(isa1(array[i], index))num1[0] ^= array[i];elsenum2[0] ^= array[i];}}public boolean isa1(int i, int index){i = i >> index;return (i & 1) == 1;} }

總結(jié)

以上是生活随笔為你收集整理的[剑指offer] 数组中只出现一次的数字的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。