У меня есть двумерный массив, индекс внешнего массива представляет собой StateID, а целые числа во внутренних массивах представляют идентификаторы StoreID.
StoreStateList = [[1,2],[1,2,3],[1,3,7,9],[1,8,12],[7,9,12]]
Я пытаюсь найти штат, в котором есть магазин, которого нет ни в одном другом штате. например состояние 3 с StoreID 8.
Моя текущая реализация состоит из 4 вложенных циклов, что кажется неэффективным. Кто-нибудь знает, как я могу сделать функцию более эффективной?
function findUniqueStore(StoreRegionList)
for state in range(len(StoreRegionList):
state_count = 0
for store in StoreStateList[state]:
// check if the store in the state occurs in any other state
for state_inner in range(len(StoreRegionList)):
for store_inner in StoreStateList[state_inner]:
if store == store_inner:
state_count += 1
if state_count == 1:
return state
Это базовый псевдокод, но я планирую реализовать его на питоне.
Вы можете использовать два набора Python для хранения потенциальных уникальных элементов и посещаемых элементов. Внутри ваших двух первых циклов for проверьте, был ли уже виден текущий элемент, если нет, добавьте его к потенциальным уникальным элементам или иным образом удалите его из уникальных элементов, если он все еще существует:
def findUniqueStore(StoreRegionList):
visitedNumbers = set()
uniqueNumbers = set()
for state in range(len(StoreRegionList):
for store in StoreStateList[state]:
// check if the store in the state occurs in any other state
if store not in visitedNumbers:
uniqueNumbers.add(store)
visitedNumbers.add(store)
elif store in uniqueNumbers:
uniqueNumbers.remove(store)
if len(uniqueNumbers)>0:
return next(iter(uniqueNumbers))
Это дает решение nlog(n), где n — общее количество элементов, в отличие от n² для вашего.
Редактировать: я не понимал, что вы явно не запрашивали решение для Python, но дело в том, что вы можете использовать наборы, которые есть в стандартной библиотеке каждого языка и обычно реализуются со сбалансированными двоичными деревьями для поддержки вставки, проверки и удаления элементов в журнале (н) время.
Это почти то, что мне было нужно. Однако мне нужно вернуть номер штата, а не номер магазина. Я пытался настроить ваш код с помощью переменной состояния, но не смог заставить его работать (пока). У вас есть решение, которое возвращает состояние? Большое спасибо!
Вы можете использовать словарь Python (то есть хеш-таблицу) вместо набора uniqueNumbers
для хранения значения состояния, связанного с потенциальными уникальными числами (ключ = хранилище, значение = состояние). Синтаксис проверки ключа в словаре аналогичен проверке наличия элемента в наборе. В конце верните uniqueNumbers[next(iter(uniqueNumbers))]
.
вы можете использовать наборы, которые есть в стандартной библиотеке каждого языка" Эээ... Серьезно?!
@CJK Конечно, каждый может быть преувеличением, но он определенно есть в стандартных библиотеках большинства языков программирования, и пока вы используете что-то, предназначенное для выполнения алгоритмов и немного популярное, первый результат Google расскажет вам, как объявлять наборы.
Вы уже отступили от каждого и добавили немного популярное предостережение, которое вы можете использовать в обоих случаях, и вы все равно будете продавать вопиющую ложь. Есть C, Assembly, Fortran, Lisp (и многие языки функционального программирования, если на то пошло), Perl, большинство языков сценариев оболочки, Awk, AppleScript, XSLT, SQL (хотя он обеспечивает операции Set), PHP, Logo (по-прежнему популярен, особенно в школы), Visual Basic (последнее, что я помню), ... Побочный вопрос: существуют ли какие-либо языки, не предназначенные для алгоритмов?
какой язык программирования вы используете? Это
Python
?