整型数组中其他数出现k次找出只出现1次的数

在其他数都出现k次的数组中找到只出现一次的数

整型数组中其他数都出现k次找到唯一出现1次的数

【题目】
给定一个整型（32位整数）数组arr和一个大于1的整数k。
已知arr中只有1个数出现了1次，其他的数都出现了k次，请返回只出现了1次的数。

【要求】
时间复杂度为$O(N)$O(N)，额外空间复杂度为$O(1)$O(1)。

算法思路

无进位k进制求和

1. 将每个整数转换为k进制数组
2. 无进位相加
3. 将最终的结果转换为整型

出现k次的数在无进位相加过程中必定得到0，因此最终的结果即为只出现了1次的数的k进制表示。

注意：
无进位相加即舍弃向前位的进位。

整型包括负数，k进制数组转换需要使用取余操作。
java的取余是向上取余，而python的取余是向下取余，针对本题需要额外处理。
举例说明其区别。
向上取余: -1 % 3 = 0 … -1
向下取余: -1 % 3 = -1 … 2。若不限制向下取余，-1可以无限转换。
解决方法

1. abs(num) < k即停止取余操作；
2. 无进位相加时保留符号位，将绝对值取余，再添加符号位。
   
   

相应代码

# 整型数组中其他数出现k次，返回只出现1次的数
def get_once_number(arr, k):
    base_arr = [0 for i in range(32)]
    for i in range(len(arr)):
        add_arr = convert_to_k_base(arr[i], k)
        half_add(base_arr, add_arr, k)
    return generate_number(base_arr, k)

# 数值转换为k进制
def convert_to_k_base(num, k):
    base_arr = [0 for i in range(32)]
    j = 0
    while num != 0 and j < len(base_arr):
        # 将负数的向下取整求余转换成向上取整
        if abs(num) < k:
            base_arr[len(base_arr) - 1 - j] = num
            break
        base_arr[len(base_arr) - 1 - j] = num % k
        num = num // k
        j += 1
    return base_arr

# 无进位加法
def half_add(base_arr, add_arr, k):
    for i in range(len(base_arr)):
        res = base_arr[i] + add_arr[i]
        sign = 1
        if res < 0:
            sign = -1
            res = - res
        # 结果绝对值求余，再加符号
        base_arr[i] = sign * (res % k)


# k进制转换为数值
def generate_number(base_arr, k):
    num = 0
    for bit in base_arr:
        num = num * k + bit
    return num

# 简单测试
if __name__ == '__main__':
    arr = [1, 1, 1, 1, 1, 3]
    k = 5
    print(get_once_number(arr, k))  # 3

    arr = [1, 1, 2, 2, 3]
    k = 2
    print(get_once_number(arr, k))  # 3

    arr = [3, 3, 3, 2, 2, 2, 1]
    k = 3
    print(get_once_number(arr, k))  # 1

    arr = [-3, -3, -3, -2, -2, -2, -1]
    k = 3
    print(get_once_number(arr, k))  # -1

有任何疑问和建议，欢迎在评论区留言和指正！

感谢您所花费的时间与精力！