Блог

Я пытаюсь решить домашнюю задачу.

В. Предположим существование двух массивов X и Y по m элементов в каждом. Предположим, что они могут содержать дубликаты (т. Е. повторяющиеся элементы), для которых определено отношение общего порядка. a) Разработайте эффективный алгоритм для определения, содержат ли X и Y один и тот же набор элементов.

Теперь, чтобы сделать это максимально эффективным, кто-то предложил использовать хэш-таблицы. Я пытался это реализовать.

Я уже создал массивы и хеш-таблицу, затем я импортировал один массив в хеш-таблицу.

На данный момент я ищу наиболее эффективный способ поиска в массиве и дайте мне ответ.

 dict = {'0':'-','1':'a','2':'b','3':'c'} #declare dictionary

print "first element of dict = ", dict['0']

print "n"

array1 = ["4","5","6","7","8","9","10"]
print "array 1 = ", array1
array2 = ["4","5","6","7","8","9","10"]
print "array 2 = ", array2

print "n"

print "array1[3] = ", array1[3]

print "n"

print "clearing dictionary..."
dict.clear(); 

print "dict = ", dict

print "n"

x = 0 #iterator for array1

print "importing array1 into dictionary..."

while x < len(array1) :
    dict[x] = array1[x]
    x  = 1

print dict

y = 0 #iterator for array2

while y < len(array2) :
    if dict
  

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

Это мое решение. Является ли это наиболее эффективным решением? Какова будет временная сложность? Я предполагаю, что O (n). Я прав?

 # define first array
array1 = ["1","1","1","2"]
print "array 1 = ", array1

#define second array
array2 = ["1","2","3"]
print "array 2 = ", array2

#function
def is_empty(x, y):

    #find set difference between first and second array
    difference1 = set(x) - set(y)
    print difference1

    #find set difference between second and first array
    difference2 = set(y) - set(x)
    print difference2

    #union two differences together
    finalset = difference1.union(difference2)
    print finalset

    #if there are elements in finalset, arrays do not contain same set of elements
    if finalset:
        print('The sets do not contain the same set of elements.')
        return False

    #if there are no elements in final set, arrays contain same set of elements
    else:
        print('The sets contain the same set of elements.')
        return True

#function call on two arrays
is_empty(array1, array2)