2.2 OddOccurrencesInArray.md

Lesson_2 Arrays 数组

P2.2 OddOccurrencesInArray

Find value that occurs in odd number of elements.

• P2.2 次数为奇数的值

找出数组中出现次数为奇数的值

给定一个非空数组A，包含有N个整数，起始下标为0。数组包含有奇数个元素，其中除了唯一一个元素之外，其他每个元素都可以与数组中另一个有相同值的元素配对。

比如，在下面这个数组中：

A[0] = 9，A[1] = 3，A[2] = 9，A[3] = 3，A[4] = 9，A[5] = 7，A[6] = 9

下标为0和2的元素的值是9；下标为1和3的元素的值是3；下标为4和6的元素的值是9；下标为5的元素的值是7，无法配对。

写一个函数：

def solution(A)

对满足上述条件的数组 A，返回数组中无法配对的元素的值。

比如，对于上面给出的数组A，函数应该返回 7。

假定:

1. N是[1，2，……，1,000,000]中的奇数；
2. 数组A每个元素的取值范围为[1，1,000,000,000]；
3. 每个数组中有且仅有一个满足条件的数；

• 解题思路

  寻找无法配对的元素，也就是寻找数组中出现的次数为奇数的元素。利用字典存储每个元素出现的次数，然后再遍历字典。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 2：Arrays
# P 2.2 OddOccurrencesInArray


def solution_list(A):
    """
    寻找数组A中出现的次数为奇数的元素,复杂度O(N**2)
    :param A: 列表形式数组
    :return: 元素
    """
    number_only = list(set(A))
    for i in number_only:
        if A.count(i) % 2 == 1:
            return i


def solution(A):
    """
    寻找数组A中出现的次数为奇数的元素,复杂度O(N) or O(N*log(N))
    :param A: 列表形式数组
    :return: 元素
    """
    times_dict = {}
    for i in A:
        if i in times_dict:
            times_dict[i] += 1
        else:
            times_dict[i] = 1
    for k in times_dict:
        if times_dict[k] % 2 == 1:
            return k

• 结果