Найти число из набора, которого нет в массиве

Question

Мне задали этот вопрос в интервью: вам дают набор чисел {1..N} и массив A [N-1]. Найдите число из набора, которого нет в массиве. Ниже приведены код и псевдокод, которые у меня есть, которые не работают.

Я предполагаю, что в наборе есть одно (и только одно) число, которого нет в массиве

1. l oop через каждый элемент в наборе
2. l oop через каждый элемент в массиве O (n)
3. проверить, есть ли число в массив
4. , если это так, ничего не делать
5. иначе, досрочно вернуть число

def findMissingNo(arr, s):  
    for num in s: #loop through each element in the set
        for num2 in arr: ##loop through each element in the array O(n)
            if (num == num2): #if the number in the set is in the array, break 
                break
        print (num)
        return num #if the number in the set is not in the array, early return the number 
    return -1 #return -1 if there is no missing element 

s1 = {1,4,5}
arr1 = [1,4]

findMissingNo(arr1, s1)

Answer 1

Если я правильно понял ваш вопрос, то вы находите эффективный способ найти число set, которого нет в list. Я вижу, вы внутри цикла, который будет O(n^2). Я бы предложил сделать dict для list, который будет O(n), а затем найти O(1) элемент в dictionay, выполнив цикл set O(n). Учитывая большой list с подмножеством set:

def findMissingNo(arr_list, s_list):
    d = dict()
    for el in arr_list:
        d.update({el: el})
    for s in s_list:  
        try:
            d[s]
            pass
        except KeyError:
            return s
    return -1 

s1 = {1,4,5}
arr1 = [1,4]

findMissingNo(arr1, s1)

Надеюсь, это поможет:)

Answer 2

По определению, у нас есть набор от 1 до N и массив размером N-1, содержащий числа от 1 до N, при этом отсутствует одно число, и мы должны найти это число

, поскольку только 1 число отсутствует, и множество имеет n элементов, а массив имеет n-1 элемент. поэтому массив является подмножеством множества с отсутствующим элементом как отсутствующим, что означает

all_number_of_set = all_number_of_array + missing_number

также

sum_of_all_number_of_set = sum_of_array_number + missing_number

, что подразумевает

missing_number = sum_of_all_number_of_set - sum_of_array_number

псевдокод

def findMissingNo(set_, arr_ ):
      return sum(set_) - sum(arr_)

Answer 3

Ваша функция квадратична c, потому что она должна проверять весь список для каждого элемента в наборе.

Важно, чтобы вы не повторяли набор. Да, это может сработать, но вы показываете, что не знаете преимуществ в сложности времени, которые вы можете получить из набора или изречения в python (или в целом в хеш-таблицах). Но вы также не можете перебирать список, потому что отсутствующий элемент ... отсутствует. Так что вы не найдете его там.

Вместо этого вы строите набор из списка и используете функцию разности. Или лучше, symbric_difference (^) см. https://docs.python.org/3.8/library/stdtypes.html#set

def findMissingNo(arr, s):        
    d = set(arr) ^ s # symmetric difference
    if 1 == len(d):
        for item in d:
            return item

print (findMissingNo([1,4], {1,4,5}))

5

Я выбрал несколько ярлыков, потому что знал, что мы хотим один предмета, и я знал, в каком контейнере он должен был находиться. Я решил вернуть None, если предмет не был найден, но я не проверял наличие нескольких предметов.

Answer 4

Как насчет чего-то вроде:

def findMissingNo(arr, s):
    for num in s:  # loop through each element in the set
        if num in arr:
            pass
        else:
            return num  # if the number in the set is not in the array, early return the number 
    return -1  # return -1 if there is no missing element