Python: проверьте, содержат ли два массива (могут содержать повторяющиеся элементы) одинаковый набор элементов - PullRequest
Новая
       30

Python: проверьте, содержат ли два массива (могут содержать повторяющиеся элементы) одинаковый набор элементов

0 голосов
/ 03 апреля 2019

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

Q.Предположим, что существуют два массива 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

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

1 Ответ

0 голосов
/ 03 апреля 2019

Это моё решение. Это самое эффективное решение? Какова будет сложность времени? Я предполагаю 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)
...