70208

Algorithm to find shortest continuous subarray that contains all values from a set

<h3>Question</h3>

I have the following problem to solve:

Given a set of integers, e.g. {1,3,2}, and an array of random integers, e.g.

[1, 2, 2, -5, -4, 0, 1, 1, 2, 2, 0, 3,3]

Find the shortest continuous subarray that contains all of the values from the set. If the subarray can not be found, return an empty array.

Result: [1, 2, 2, 0, 3]

Or

[1, 2, 2, -5, -4, 3, 1, 1, 2, 0], {1,3,2}.

Result: [3, 1, 1, 2]

I have tried the following put there seems to be something wrong with my second loop. I'm not sure what I need to change:

def find_sub(l, s): i = 0 counts = dict() end = 0 while i < len(s): curr = l[end] if curr in s: if curr in counts: counts[curr] = counts[curr] + 1 else: counts[curr] = 1 i += 1 end += 1 curr_len = end start = 0 for curr in l: if curr in counts: if counts[curr] == 1: if end < len(l): next_item = l[end] if next_item in counts: counts[next_item] += 1 end += 1 else: counts[curr] -= 1 start += 1 else: start += 1 if (end - start) < curr_len: return l[start:end] else: return l[:curr_len]
<h3>Answer1:</h3>

You are using two-pointer approach, but move both indexes only once - until the first match found. You should repeat move right - move left pattern to get the best index interval.

def find_sub(l, s): left = 0 right = 0 ac = 0 lens = len(s) map = dict(zip(s, [0]*lens)) minlen = 100000 while left < len(l): while right < len(l): curr = l[right] right += 1 if curr in s: c = map[curr] map[curr] = c + 1 if c==0: ac+=1 if ac == lens: break if ac < lens: break while left < right: curr = l[left] left += 1 if curr in s: c = map[curr] map[curr] = c - 1 if c==1: ac-=1 break if right - left + 1 < minlen: minlen = right - left + 1 bestleft = left - 1 bestright = right return l[bestleft:bestright] print(find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 0, 3, 3], {1,3,2})) print(find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 1, 0, 3, 3], {1,3,2})) >>[2, -5, -4, 3, 1] >>[2, 1, 0, 3]
<h3>Answer2:</h3>

You can use a sliding window approach (using a generator), the idea is to generate all subsets of size n (size of the set) to size N (size of the list), and check if any of them exists, stopping when finding the first one:

from itertools import islice, chain def window(seq, n=2): "Returns a sliding window (of width n) over data from the iterable" " s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ... " it = iter(seq) result = tuple(islice(it, n)) if len(result) == n: yield result for elem in it: result = result[1:] + (elem,) yield result l = [1, 2, 2, -5, -4, 3, 1, 1, 2, 0] s = {1,3,2} def minimum_subset(l, s): for w in chain.from_iterable(window(l, i) for i in range(len(s), len(l)+1)): if s == set(w): return w return [] print(minimum_subset(l, s))

Result (3, 1, 1, 2) Here you have the live example


<h3>Answer3:</h3>

This should be the most performant solution, running in O(n):

def find_sub(l, s): if len(l) < len(s): return None # Keep track of how many elements are in the interval counters = {e: 0 for e in s} # Current and best interval lo = hi = 0 best_lo = 0 best_hi = len(l) # Increment hi until all elements are in the interval missing_elements = set(s) while hi < len(l) and missing_elements: e = l[hi] if e in counters: counters[e] += 1 if e in missing_elements: missing_elements.remove(e) hi += 1 if missing_elements: # Array does not contain all needed elements return None # Move the two pointers missing_element = None while hi < len(l): if missing_element is None: # We have all the elements if hi - lo < best_hi - best_lo: best_lo = lo best_hi = hi # Increment lo e = l[lo] if e in counters: counters[e] -= 1 if counters[e] == 0: missing_element = e lo += 1 else: # We need more elements, increment hi e = l[hi] if e in counters: counters[e] += 1 if missing_element == e: missing_element = None hi += 1 return l[best_lo:best_hi] assert find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 0, 3, 3], {1, 3, 2}) == [2, -5, -4, 3, 1] assert find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 1, 0, 3, 3], {1, 3, 2}) == [2, 1, 0, 3] assert find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 1, 0, 3, 3], {1, 3, 7}) is None
<h3>Answer4:</h3>

Joining in the fun, here's my attempt. I'm not familiar with algorithm names, but this would seem like a sliding window approach based on @Netwave's description for his answer.

I = {1, 3, 2} A = [1, 2, 2, -5, -4, 0, 1, 1, 2, 2, 0, 3, 3] setcount = {i: 0 for i in I} stage = [] shortest = A for i in range(len(A)): # Subset stage.append(A[i]) # Update the count if A[i] in I: setcount[A[i]] += 1 while 0 not in setcount.values(): # Check if new subset is shorter than existing's if len(stage) < len(shortest): shortest = stage.copy() # Consume the head to get progressively shorter subsets if stage[0] in I: setcount[stage[0]] -= 1 stage.pop(0) >>>print(shortest) [1, 2, 2, 0, 3]

来源:https://stackoverflow.com/questions/56000424/algorithm-to-find-shortest-continuous-subarray-that-contains-all-values-from-a-s

Recommend

  • Python os.access() reads file no matter what
  • Monitor CPU and memory consumption of a specific processes in (Windows) C?
  • HTML5 Drag & Drop change cursor while dragging (don't use UI)
  • Trying to understand setf + aref “magic”
  • How do I debug an Android app that crashes only in Release Mode
  • How to use a boost::mutex as the mapped type in std::map?
  • Ember : downgrading ember with bower install
  • Crossbrowser “inArray” function (without jQuery)
  • How to fix `unknown variable 'sql-mode=ANSI'`?
  • How do I set the FallbackValue for a Binding on UIElement.Margin?
  • Exception in Boto3 - botocore.exceptions.EndpointConnectionError
  • get div height after div content load
  • How to create a Graphics2D instance?
  • Memory leak when resizing UIImage
  • Cloudflare service worker code to “Bypass cache on cookie” not working
  • JQuery Validation for Duplicates in Form Array
  • how can i have scrollbar when position is negative?
  • jre_home environment variable is not defined correctly while starting tomcat
  • exception thrown while building the java application using netbeans
  • getting exception when inserting events in android calendar
  • Problem with installing Charm-Crypto for Python3
  • How to smoothly connect two signals in matlab [closed]
  • How to create mirrored image effect with CSS single element
  • No Gradle file syntax highlighting in Eclipse Mars.2
  • Can't hide status bar in AVPlayerViewController's portrait mode
  • How to convert days into months using datetime in Python3?
  • Year over Year Stats from a Crossfilter Dataset
  • xpath assertion failure with dynamic xpath
  • how to run a different select statement based on condition in Hive SQL
  • JavaScript Regex to Match Boundaries of Words with diacritics
  • How to turn off notice reporting in xampp?
  • How to handle div that is created dynamically in a table
  • Debug `Unexpected end of JSON input Error` on content script
  • Firebase: How to read from external DB?
  • PHP Permalinks.. how to change?
  • media foundation H264 decoder not working properly
  • Running R's aov() mixed effects model from Python using rpy2
  • Access to a Matlab gui from the web
  • convert json to excel in java