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

: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
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 Like
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
def find_odd(nums:list):
    for i in nums:
        if nums.count(i)%2==1:
            return i

多个奇数咋办

def find_odd(nums:list) -> int:
    for num in nums:
        if nums.count(num) %2 ==1:
            return num

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

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

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

: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内置的集合模块collectionsCounter类实现特定条件的统计。

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 Like
关闭