個人中心
退出
劍指offer之求數(shù)組里面只出現(xiàn)一次的的兩個數(shù)據(jù)
1 問題
一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。
2 分析
第一種方法：我們用位運(yùn)算
我們想到位運(yùn)算
（1） a^a=0
（2）a^0=a
（2）a^b^c=a^(b^c)=(a^c)^b
1) 對所有運(yùn)算進(jìn)行異或運(yùn)算，最后結(jié)果就是兩個出現(xiàn)一次的元素異或結(jié)果，接下來問題演變成了我們知道兩個不同數(shù)據(jù)的異或值，那么怎么求出這兩個值呢？
2) 因?yàn)檫@兩個元素不相等，所以異或的結(jié)果肯定不是0，也就是可以再異或的結(jié)果中找到1位不為0的位，例如異或結(jié)果的最后一位為1，我們把這個位置標(biāo)記為index,然后我們把原始數(shù)組分為2個數(shù)組，第一個數(shù)組中的每個數(shù)組的第index位都是1的數(shù)組和每個數(shù)組的第index位都是0的數(shù)組，然后我們再把這個兩組數(shù)據(jù)進(jìn)行異或處理，分別求出的數(shù)據(jù)就是我們不同的兩個數(shù)。
第二種方法：我們用map,key為元素值，如果出現(xiàn)幾次放進(jìn)value里面去，然后最后遍歷如果value是1的話，我們得到2個key就行。
3 代碼實(shí)現(xiàn)
用異或處理的C++版本如下
#include <iostream>
#include <vector>
using namespace std;
void findApperanceTwoNumber(vector<int>& input, int& num1, int& num2)
{
if (input.size() < 2)
{
std::cout << "input.size() < 2" << std::endl;
return;
}
int sum = 0;
//對所有數(shù)據(jù)進(jìn)行異或處理
for (int i = 0; i < input.size(); ++i)
{
sum ^= input[i];
}
//我們通過index找到這個2個不同元素異或值的位1的位置
int index = 0;
for (int i = 0; i < 32; ++i)
{
if (((sum >> i) & 1) == 1)
{
index = i;
break;
}
}
//然后我們遍歷數(shù)組把每個數(shù)據(jù)的第index位和1進(jìn)行異或處理，分別得到結(jié)果為1和0的2組數(shù)據(jù)，然后把這2組數(shù)據(jù)分別異或處理的和就是2個不同的數(shù)據(jù)
for (int i = 0; i < input.size(); ++i)
{
if (((input[i] >> index) & 1) == 1)
{
num1 ^= input[i];
}
else
{
num2 ^= input[i];
}
}
}
int main()
{
vector<int> v2;
v2.push_back(2);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
v2.push_back(6);
v2.push_back(6);
int a = 0, b = 0;
findApperanceTwoNumber(v2, a, b);
std::cout << "a is "<< a << " b is " << b << std::endl;
return 0;
}
用map處理的C++版本如下
#include <iostream>
#include <vector>
#include <map>
using namespace std;
void findApperanceTwoNumber2(vector<int>& input, int& num1, int& num2)
{
if (input.size() < 2)
{
std::cout << "input.size() < 2" << std::endl;
return;
}
map<int, int> datas;
for (int i = 0; i < input.size(); ++i)
{
//C++里面map如果要通過key獲取value的話，我們先需要探測map里面是不是有這個key，我們可以count函數(shù),這里如果是java版本的話，就算key不存在的話，我們執(zhí)行g(shù)et方法操作，得到的null,沒關(guān)系。
if (datas.count(input[i]))
{
if (datas[input[i]] == 1)
{
//這里用數(shù)組形式是因?yàn)槿绻胕nsert如果發(fā)現(xiàn)key一樣的話，再次插入會失敗，我們所以用數(shù)組的形式，這里是通過key更新value
datas[input[i]] = 2;
}
}
else
{
datas[input[i]] = 1;
}
}
///然后我們再遍歷map
for (map<int, int>::iterator it = datas.begin(); it != datas.end(); ++it)
{
if (it->second == 1)
{
if (num1 == 0)
{
//這里是獲取key
num1 = it->first;
}
else
{
//這里是獲取value
num2 = it->first;
}
}
}
}
int main()
{
vector<int> v2;
v2.push_back(2);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
v2.push_back(6);
v2.push_back(6);
int a = 0, b = 0;
findApperanceTwoNumber2(v2, a, b);
std::cout << "a is "<< a << " b is " << b << std::endl;
return 0;
}
運(yùn)行結(jié)果如下
a is 3 b is 4
用map處理的java版本如下
import java.io.*;
import java.util.ArrayList;
import java.util.*;
class St
{
public St() {}
ArrayList<Integer> findApperanceTwoNumber2(int[] datas) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (datas == null || datas.length < 2)
return list;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < datas.length; ++i) {
if (map.containsKey(datas[i])) {
if (map.get(datas[i]) == 1)
{
map.put(datas[i], 2);
}
} else {
map.put(datas[i], 1);
}
}
Set<Integer> keys = map.keySet();
for (int key : keys) {
if (map.get(key) == 1) {
list.add(key);
}
}
return list;
}
}
class test
{
public static void main (String[] args) throws java.lang.Exception
{
ArrayList<Integer> list = new ArrayList<Integer>();
St s = new St();
int [] a = {1, 1, 3, 5, 4, 4};
list = s.findApperanceTwoNumber2(a);
for (int i : list)
{
System.out.println("value is " + i);
}
}
}
運(yùn)行結(jié)果如下
value is 3
value is 5
4 總結(jié)
如果我們有2個不同數(shù)的異或值，那我們怎么知道這2個數(shù)據(jù)值呢？（這里不是說直接知道這2個元素的數(shù)組意思，不然還要你求干吊） 因?yàn)檫@兩個元素不相等，所以異或的結(jié)果肯定不是0，也就是可以再異或的結(jié)果中找到1位不為0的位，例如異或結(jié)果的最后一位為1，我們把這個位置標(biāo)記為index,然后我們把原始數(shù)組分為2個數(shù)組，第一個數(shù)組中的每個數(shù)組的第index位都是1的數(shù)組和每個數(shù)組的第index位都是0的數(shù)組，然后我們再把這個兩組數(shù)據(jù)進(jìn)行異或處理，分別求出的數(shù)據(jù)就是我們不同的兩個數(shù)。
C++版本的map操作，我們最好是用數(shù)組形式，因?yàn)閿?shù)組形式既可以賦值和可以用來進(jìn)行修改操作，如果是用insert函數(shù)插入的當(dāng)key是同樣而value不是同樣值的時候會失敗，然后我們獲取的話最好也是通過數(shù)組形式的key獲取，但是獲取之前我們需要判斷key是否存在map里面的key沒有，如果沒在的話，直接獲取就有問題，但是java的話，就算沒有key,獲取的也是null值，沒關(guān)系。
C++的話我們map用count(key)函數(shù)來判斷是否key存在，而java的話，我么可以用map的containsKey(key)函數(shù)判斷key是否存在，無論在C++版本還是java版本，我們要對map通過key獲取value操作，如果不是通過keySet來獲取（就是這個key必然存在map里面的時候），我們都要先用上面的函數(shù)進(jìn)行探測是否包含key,這樣代碼的健壯性好點(diǎn)。
作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)
分類導(dǎo)航