How to find unique number in 2D Array-CodePudding

I have a 2D array, the index of the outer array represents the StateID and the integers in the inner arrays represent the StoreIDs.

StoreStateList = [[1,2],[1,2,3],[1,3,7,9],[1,8,12],[7,9,12]]

I am trying to find a state that has a store that no other state has. e.g. state 3 with StoreID 8.

My current implementation consists of 4 nested loops which appears inefficient. Does anyone know how I can make the function more efficient?

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

CodePudding user response：

You can use two python sets to store potential unique elements and visited elements. Inside your two first for loops, check if the current element has already been seen, if not add it to potential unique elements or otherwise remove it from unique elements if it is still there :

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))

This gives a nlog(n) solution where n is the total number of elements, as opposed to n² for yours.

Edit : I did not realise you didn't explicitly asked for a python solution, but the point is you can use sets which are in every language's standard library and usually implemented with balanced binary trees to support insertion, check and deletion of elements in log(n) time.