剑指offer之求数组里面只出现一次的的两个数据

1 问题

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

2 分析

第一种方法:我们用位运算

我们想到位运算

(1) a^a=0

(2)a^0=a

(2)a^b^c=a^(b^c)=(a^c)^b

1) 对所有运算进行异或运算,最后结果就是两个出现一次的元素异或结果,接下来问题演变成了我们知道两个不同数据的异或值,那么怎么求出这两个值呢?

2) 因为这两个元素不相等,所以异或的结果肯定不是0,也就是可以再异或的结果中找到1位不为0的位,例如异或结果的最后一位为1,我们把这个位置标记为index,然后我们把原始数组分为2个数组,第一个数组中的每个数组的第index位都是1的数组和每个数组的第index位都是0的数组,然后我们再把这个两组数据进行异或处理,分别求出的数据就是我们不同的两个数。

第二种方法:我们用map,key为元素值,如果出现几次放进value里面去,然后最后遍历如果value是1的话,我们得到2个key就行。

3 代码实现

用异或处理的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;
    //对所有数据进行异或处理
    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;
        }
    }
    //然后我们遍历数组把每个数据的第index位和1进行异或处理,分别得到结果为1和0的2组数据,然后把这2组数据分别异或处理的和就是2个不同的数据
    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函数,这里如果是java版本的话,就算key不存在的话,我们执行get方法操作,得到的null,没关系。
        if (datas.count(input[i]))
        {
            if (datas[input[i]] == 1)
            {
                //这里用数组形式是因为如果用insert如果发现key一样的话,再次插入会失败,我们所以用数组的形式,这里是通过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;
}

运行结果如下

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);
    }
}
}

运行结果如下

value is 3
value is 5

4 总结

如果我们有2个不同数的异或值,那我们怎么知道这2个数据值呢?(这里不是说直接知道这2个元素的数组意思,不然还要你求干吊) 因为这两个元素不相等,所以异或的结果肯定不是0,也就是可以再异或的结果中找到1位不为0的位,例如异或结果的最后一位为1,我们把这个位置标记为index,然后我们把原始数组分为2个数组,第一个数组中的每个数组的第index位都是1的数组和每个数组的第index位都是0的数组,然后我们再把这个两组数据进行异或处理,分别求出的数据就是我们不同的两个数。

C++版本的map操作,我们最好是用数组形式,因为数组形式既可以赋值和可以用来进行修改操作,如果是用insert函数插入的当key是同样而value不是同样值的时候会失败,然后我们获取的话最好也是通过数组形式的key获取,但是获取之前我们需要判断key是否存在map里面的key没有,如果没在的话,直接获取就有问题,但是java的话,就算没有key,获取的也是null值,没关系。

C++的话我们map用count(key)函数来判断是否key存在,而java的话,我么可以用map的containsKey(key)函数判断key是否存在,无论在C++版本还是java版本,我们要对map通过key获取value操作,如果不是通过keySet来获取(就是这个key必然存在map里面的时候),我们都要先用上面的函数进行探测是否包含key,这样代码的健壮性好点。

(0)

相关推荐