【每日一题0817】寻找奇数次数元素

兴趣爱好交流 每日一题
1

:woman_mage:给定一个由数字组成的列表，请编写一个python函数，找出其中唯一一个出现奇数次数的元素。

示例：
输入：[8] ，输出：8 ，因为8出现了1次（奇数）。
输入：[1,1,2] ，输出：2 ，因为2出现了1次（奇数）。
输入：[0,1,0,1,0] ，输出：0 ，因为0出现了3次（奇数）。

题目难度：简单
题目来源：codewars

def find_odd(nums:list) -> int:
    pass
  
assert find_odd([8]) == 8
assert find_odd([1, 1, 2]) == 2
assert find_odd([0,1,0,1,0]) == 0
assert find_odd([1,2,2,3,3,3,4,3,3,3,2,2,1]) == 4
2 
from collections import Counter

def find_odd(nums: list) -> int:
    return [k for k, v in Counter(nums).items() if v % 2 == 1][0]

assert find_odd([8]) == 8
assert find_odd([1, 1, 2]) == 2
assert find_odd([0, 1, 0, 1, 0]) == 0
assert find_odd([1, 2, 2, 3, 3, 3, 4, 3, 3, 3, 2, 2, 1]) == 4
1 个赞
3 
def find_odd(nums: list) -> int:
    dict = {}
    for i in nums:
        if i in dict:
            dict[i] = dict[i] + 1
        else:
            dict[i] = 1
    return [k for k , v in dict.items() if v % 2 == 1][0]

assert find_odd([8]) == 8
assert find_odd([1, 1, 2]) == 2
assert find_odd([0, 1, 0, 1, 0]) == 0
assert find_odd([1, 2, 2, 3, 3, 3, 4, 3, 3, 3, 2, 2, 1]) == 4
4 
def find_odd(nums:list):
    for i in nums:
        if nums.count(i)%2==1:
            return i
5

多个奇数咋办

6 
def find_odd(nums:list) -> int:
    for num in nums:
        if nums.count(num) %2 ==1:
            return num
7 
def find_odd(nums: list) -> int:
    dic = {}
    for i in nums:
        if i not in dic.keys():
            dic[i] = 1
        else:
            dic[i] += 1
    for k, v in dic.items():
        if v % 2 == 1:
            return k
8

@skying0527 出现奇数次数的元素是唯一的。

9 
    public int find_add(ArrayList<Integer> arrayList) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < arrayList.size(); i++) {
            Integer key = arrayList.get(i);
            Integer value = hashMap.get(key);
            if (hashMap.containsKey(key)) {
                value++;
                hashMap.put(key, value);
            }else {
                hashMap.put(key, 1);
            }
        }
        Set<Map.Entry<Integer, Integer>> entries = hashMap.entrySet();
        Iterator<Map.Entry<Integer, Integer>> iterator = entries.iterator();
        while (iterator.hasNext()){
            Map.Entry<Integer, Integer> next = iterator.next();
            if (next.getValue() % 2 == 1){
                return next.getKey();
            }
        }
        return 0;
    }
10 
def find_odd(nums:list) -> int:
    for x in nums:
        if nums.count(x)%2!=0:
            return x

assert find_odd([8]) == 8
assert find_odd([1, 1, 2]) == 2
assert find_odd([0,1,0,1,0]) == 0
assert find_odd([1,2,2,3,3,3,4,3,3,3,2,2,1]) == 4

:partying_face: :partying_face: :partying_face: :partying_face: :partying_face: :partying_face:

11

:medal_sports:参考题解1 :medal_sports: 

def find_odd(nums:list) -> int:
    return [x for x in nums if nums.count(x) % 2][0]

assert find_odd([8]) == 8
assert find_odd([1, 1, 2]) == 2
assert find_odd([0,1,0,1,0]) == 0
assert find_odd([1,2,2,3,3,3,4,3,3,3,2,2,1]) == 4

思路：使用列表推导式。

循环统计出现奇数次的元素并构建成为一个新的列表。由于目标元素有且仅有一个，所以取列表的首个元素即可。

:medal_sports:参考题解2 :medal_sports: 

from collections import Counter

def find_odd(nums:list) -> int:
    return [k for k, v in Counter(nums).items() if v % 2 != 0][0]

assert find_odd([8]) == 8
assert find_odd([1, 1, 2]) == 2
assert find_odd([0,1,0,1,0]) == 0
assert find_odd([1,2,2,3,3,3,4,3,3,3,2,2,1]) == 4

思路：利用python3内置的集合模块collections的Counter类实现特定条件的统计。

collections模块是日常工作中的重点、高频模块，常用类型有：计数器（Counter），双向队列（deque），默认字典（defaultdict），有序字典（OrderedDict），具名元组（namedtuple）。

:medal_sports:参考思路3 :medal_sports: 

import operator
from functools import reduce

def find_odd(nums:list) -> int:
    return reduce(operator.xor, nums)

assert find_odd([8]) == 8
assert find_odd([1, 1, 2]) == 2
assert find_odd([0, 1, 0 ,1, 0]) == 0
assert find_odd([1,2,2,3,3,3,4,3,3,3,2,2,1]) == 4

思路：利用异或运算，结合归约函数reduce实现。

异或运算（XOR）除了经常在密码学中被用作对称加密外，也很适合做奇偶校验。一个数自己异或自己（出现重复）将会是0，而0异或数字n的结果一定是数字n。将这个列表全部异或一遍，结果将是刚好出现奇数次数的那个n，即得到最终结果。

注意：python3已经将 reduce() 移到 functools 模块里，需要import引入方可使用。在之前的版本曾是内置函数。

@hua123 @tingting @fwj @skying0527 @sunyanfen @747781153 @lifq1984

1 个赞