C++算法题-找出奇数

题目

同样是 codewar 的一道题

Given an array of integers, find the one that appears an odd number of times. There will always be only one integer that appears an odd number of times.

提供一个整形数组，找到一个出现了奇数次的数字并返回。只需要返回一个就行。

1
2
3
4
5


#include <vector>

int findOdd(const std::vector<int>& numbers){
  //your code here
}

实例:

[7] should return 7, because it occurs 1 time (which is odd).
[0] should return 0, because it occurs 1 time (which is odd).
[1,1,2] should return 2, because it occurs 1 time (which is odd).
[0,1,0,1,0] should return 0, because it occurs 3 times (which is odd).
[1,2,2,3,3,3,4,3,3,3,2,2,1] should return 4, because it appears 1 time (which is odd).

题解

题目内容很简单，只需要一个个遍历元素同时数出该元素一共有几个，当这个元素遍历完计数是奇数个就退出循环返回元素。
需要两个 for 循环，因为题目给的是 vector 所以可以用迭代器(iterator)来循环。
两层嵌套循环就可以解决了，代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <iostream>
#include <vector>

int findOdd(const std::vector<int>& numbers) {
    for (auto num : numbers) {
        int count = 0;
        for (auto it : numbers) {
            if (num == it) {
                count++;
            }
        }
        if (count % 2 != 0) {
            return num;
        }
    }
}

他人解法

我所写的只用到了迭代器，而 C++ 还有非常多好用的内置函数可以更好的解决问题。

`count()`

使用 <algorithm> 库内的 count()对元素进行计数可以将内循环省掉，提j高代码的阅读性。

1
2
3
4
5
6
7
8
9


#include <algorithm>
#include <vector>

int findOdd(const std::vector<int>& numbers) {
    for (auto num : numbers) {
        if (std::count(numbers.begin(), numbers.end(), num) % 2 != 0)
            return num;
    }
}

count() 的用法为:

1

count(first, last, val);

`unordered_map<>`

使用 unordered_map 数据类型可以将每一个元素出现的次数整合在一起。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


#include <vector>
#include <unordered_map>

int findOdd(const std::vector<int>& numbers) {
    std::unordered_map<int, int> count;
    for (const auto it : numbers){
        count[it]++;
    }
    for (const auto it : count){
        if(it.second % 2 != 0){
            return it.first;
        }
    }
}