如何找出int数组中只出现一次的两个元素（其它所有元素都出现了两次）？

2020-03-31

总阅读量6次

问题描述

在一个int类型的数组中除有两个元素各出现了一次外，其它元素都出现了两次，最好能保证最好的时空效率。

算法一

回溯算法：

#include <iostream>

using namespace std;

int main()
{

    int len = 0;
    //接受用户输入的数组长度
    cout << "please input the array length: " ;
    cin >> len;

    int a[len];

	//接受用户输入的数组元素
    cout << "please the array's elements:" << endl;
    for(int i = 0;i < len;i++){
        cin >> a[i];
    }


    int temp = 0;//正在检测的数组元素下标
    int i = 0;//记录待检测数组元素下标

    while(temp < len){
		/*如果temp元素与i相等并且temp不等于i（因为初始值中temp = i）
		或者temp元素已经检测过*/
        if((a[temp] == a[i] && temp != i) || a[temp] == -1){
            /*标记已经检测过的元素，这个标记是int数组中被限定输入的值
            读者可以根据需要指定，这里为了方便说明采用‘-1’标记*/
            a[temp] = -1;
            a[i] = -1;
            i = ++temp;
        }
        //i大于数组长度后，表示正在检测的元素只出现了一次
        else if (i >= len){
            cout << a[temp] << " ";
            i = ++temp;
        }
        //不满足上述分支条件，i指向下一个元素
        else
            i ++;
    }


    return 0;
}

测试结果：

test1:
result1
test2:
result2
test3:
result3

评价：

空间复杂度为O(1)，时间复杂度上大于 O(n)小于等于O(n^2),
空间上达到要求，时间上未达到要求，需要改进算法。

算法二

位运算算法：

#include <iostream>

using namespace std;

int main()
{
	//初始化待检测数组
    int arr[8] = {2,5,5,2,3,6,4,6};

    int num = 0;

	//找出数组中只出现过一次的元素的异或值
    for(int i = 0;i < 8;i ++){
        num = num ^ arr[i];
    }

    cout << "num:" << num << endl;

    int temp = 1;
	/*从最低位开始找出两个元素第一次不同的位，即num中从最低位第一次出现1的地方*/
    while((temp & num) == 0){
        temp <<= 1;
    }

    cout << "temp:" << temp << endl;

    int num1 = 0;
    int num2 = 0;

//用按位与运算将这两个数分开，分别按位异或，（一个数自己与自己异或为0）
    for(int i = 0;i < 8;i ++){
        if((temp & arr[i]) == 0)
            num1 ^= arr[i];
        else
            num2 ^= arr[i];
    }

    cout << "num1:" << num1 <<endl;
    cout << "num2:" << num2 << endl;
    return 0;
}

测试结果：

test1:
result1
读者可以自行设计测试样例进行测试

评价：
由于只遍历了一遍数组的元素，故时间复杂度为o(n)
空间复杂度为o(1),符合题目要求

—-end—