как сравнить два числа, чтобы найти количество соответствующих разных цифр - PullRequest
0 голосов
/ 29 июня 2019

У меня есть два числа 1100 и 1010, тогда я хотел бы узнать количество различных соответствующих цифр среди них, поэтому ответ для приведенного выше примера будет 2, поскольку 2-я цифра и 3-я цифра оба числаразные.

Я использую эту программу

def req_fun(arr, b): # arr :['1100', '0011', '0101', '1110'], b:'1010'
    count = 0
    for i in arr:
        for j in range(len(b)):
            count += int(i[j])^int(b[j])
    return count

Мне нужен был лучший способ добиться этого, так как я получаю TLE (превышено ограничение по времени), используя этот подход.

ПРИМЕЧАНИЕ: все цифры будут строго 0 и 1

Ответы [ 4 ]

1 голос
/ 29 июня 2019

Мне было непонятно в вопросе, что если вы хотите вернуть общее количество разных цифр или количество разных цифр для элемента в списке arr.Поэтому я предполагаю, что вы хотите вернуть общее количество различных цифр.

Если вы сложите оба числа (алгебраическую сумму), то сумма двух соответствующих цифр будет 1 тогда и только тогда, когда две цифрыразличаются, и этот факт можно использовать для подсчета количества разных цифр, как показано ниже

def count_different(arr, b):
    diff_digits = 0
    for i in arr:
        diff_digits += str(int(i)+int(b)).count('1')
    return diff_digits

, если вы хотите вернуть количество разных цифр для каждого элемента в arr они добавляют каждый счет в спискеи вернуть список.

def count_different(arr, b):
    diff_digits = 0
    l = []
    for i in arr:
        diff_digits += str(int(i)+int(b)).count('1')
        l.append(diff_digits)
    return l
1 голос
/ 29 июня 2019

Вы можете использовать чистый Python способ sum на генераторе с zip():

a, b = 1100, 1010

print(sum(x != y for x, y in zip(str(a), str(b))))
# 2
0 голосов
/ 29 июня 2019
sum(a & 2**c != b & 2**c for c in range(4))

Этот 4 - это ваш жестко закодированный лен двоичных представлений.a и b - ваши числа.

Редактировать: это sum действует как счетчик истинных значений, так как True оценивается в 1, а False в 0.

0 голосов
/ 29 июня 2019

То, что вам нужно, это расстояние Хемминга двух строк, то есть различия между двумя строками (равными по длине).

К счастью, есть также Pythonкод в Википедии , так что вы можете просто взять и использовать его.

Код:

def hamming_distance(s1, s2):
    """Return the Hamming distance between equal-length sequences"""
    if len(s1) != len(s2):
        raise ValueError("Undefined for sequences of unequal length")
    return sum(el1 != el2 for el1, el2 in zip(s1, s2))
...