编写类方法找出[1,n]区间内重复出现的整数

给定整数n（参数input2）和一个由[1, n]范围内整数组成的数组input1（每个整数仅出现1次或2次），请实现UserMainCode类的range类方法，返回数组中所有出现两次的整数。

示例 #

• 输入1: (1,1,2)
• 输入2: 3
• 输出: {1}

解法1：哈希表统计（直观易实现） #

遍历数组，用字典统计每个数字的出现次数，遇到已存在的数字就加入结果集合，最后返回该集合。这种方法逻辑简单，容易理解，时间复杂度为O(n)，空间复杂度为O(n)。

代码实现 #

class UserMainCode(object):

    @classmethod
    def range(cls, input1, input2):
        count_map = {}
        duplicates = set()
        for num in input1:
            if num in count_map:
                duplicates.add(num)
            else:
                count_map[num] = 1
        return duplicates

解法2：数组下标标记（空间优化） #

利用数组元素范围[1, n]与数组下标（0起始）的对应关系，通过修改原数组元素的符号来标记是否已访问过：遍历每个元素，取其绝对值对应的下标位置，若该位置元素为负，说明当前元素是重复项；否则将该位置元素取反标记为已访问。此方法时间复杂度O(n)，空间复杂度O(1)（结果集合除外）。

代码实现 #

class UserMainCode(object):

    @classmethod
    def range(cls, input1, input2):
        duplicates = set()
        arr = list(input1)  # 将输入元组转为可修改的列表
        for num in arr:
            idx = abs(num) - 1
            if arr[idx] < 0:
                duplicates.add(abs(num))
            else:
                arr[idx] *= -1
        return duplicates

内容的提问来源于stack exchange，提问作者Food World