Как найти уникальный номер в 2D-массиве

У меня есть двумерный массив, индекс внешнего массива представляет собой 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?

ths 12.10.2022 14:43

Это базовый псевдокод, но я планирую реализовать его на питоне.

BlackPearl 12.10.2022 14:49
Структурированный массив Numpy
Структурированный массив Numpy
Однако в реальных проектах я чаще всего имею дело со списками, состоящими из нескольких типов данных. Как мы можем использовать массивы numpy, чтобы...
T - 1Bits: Генерация последовательного массива
T - 1Bits: Генерация последовательного массива
По мере того, как мы пишем все больше кода, мы привыкаем к определенным способам действий. То тут, то там мы находим код, который заставляет нас...
Что такое деструктуризация массива в JavaScript?
Что такое деструктуризация массива в JavaScript?
Деструктуризация позволяет распаковывать значения из массивов и добавлять их в отдельные переменные.
1
2
57
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы можете использовать два набора 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, но дело в том, что вы можете использовать наборы, которые есть в стандартной библиотеке каждого языка и обычно реализуются со сбалансированными двоичными деревьями для поддержки вставки, проверки и удаления элементов в журнале (н) время.

Это почти то, что мне было нужно. Однако мне нужно вернуть номер штата, а не номер магазина. Я пытался настроить ваш код с помощью переменной состояния, но не смог заставить его работать (пока). У вас есть решение, которое возвращает состояние? Большое спасибо!

BlackPearl 12.10.2022 16:02

Вы можете использовать словарь Python (то есть хеш-таблицу) вместо набора uniqueNumbers для хранения значения состояния, связанного с потенциальными уникальными числами (ключ = хранилище, значение = состояние). Синтаксис проверки ключа в словаре аналогичен проверке наличия элемента в наборе. В конце верните uniqueNumbers[next(iter(uniqueNumbers))].

pasthec 12.10.2022 17:12

вы можете использовать наборы, которые есть в стандартной библиотеке каждого языка" Эээ... Серьезно?!

CJK 12.10.2022 18:55

@CJK Конечно, каждый может быть преувеличением, но он определенно есть в стандартных библиотеках большинства языков программирования, и пока вы используете что-то, предназначенное для выполнения алгоритмов и немного популярное, первый результат Google расскажет вам, как объявлять наборы.

pasthec 13.10.2022 10:53

Вы уже отступили от каждого и добавили немного популярное предостережение, которое вы можете использовать в обоих случаях, и вы все равно будете продавать вопиющую ложь. Есть C, Assembly, Fortran, Lisp (и многие языки функционального программирования, если на то пошло), Perl, большинство языков сценариев оболочки, Awk, AppleScript, XSLT, SQL (хотя он обеспечивает операции Set), PHP, Logo (по-прежнему популярен, особенно в школы), Visual Basic (последнее, что я помню), ... Побочный вопрос: существуют ли какие-либо языки, не предназначенные для алгоритмов?

CJK 19.10.2022 09:57

Другие вопросы по теме