Python
Data Structures · #7 / 11

Sets

अद्वितीयता + तेज़ membership

यह क्यों मायने रखता है

Sets डुप्लिकेट हटा देते हैं और औसतन O(1) membership जाँच देते हैं — कई DSA समस्याओं के लिए एकदम सही।

मूल विचार

एक set अद्वितीय, hashable items का एक थैला है जिसमें कोई क्रम नहीं होता। स्कूल वाले operations: | संघ (union), & प्रतिच्छेदन (intersection), - अंतर (difference), ^ सममित अंतर (symmetric difference)।

आज़माकर देखिए

Deduplication और membership:

nums = [1, 1, 2, 3, 3, 5, 5, 7]
unique = set(nums)
print(unique, "size:", len(unique))

print(5 in unique)   # O(1) average
print(9 in unique)
not loaded

Set बीजगणित:

a = {"red", "green", "blue", "yellow"}
b = {"green", "blue", "purple"}
print("union        ", a | b)
print("intersection ", a & b)
print("a only       ", a - b)
print("xor          ", a ^ b)
not loaded

एक चिर-परिचित interview समस्या — पहला दोहराया गया character:

def first_repeat(s):
  seen = set()
  for ch in s:
      if ch in seen:
          return ch
      seen.add(ch)
  return None

for w in ["abcdea", "abcde", "swiss"]:
  print(w, "->", first_repeat(w))
not loaded

मुख्य methods

| Method | यह क्या करता है | उदाहरण | | --- | --- | --- | | add(x) | एक जोड़ता है | st.add(3) | | update(iter) | कई जोड़ता है | st.update([4,5]) | | remove(x) | हटाता है; न मिले तो error | st.remove(2) | | discard(x) | सुरक्षित ढंग से हटाता है | st.discard(2) | | pop() | कोई एक हटाता है | st.pop() | | clear() | सब हटाता है | st.clear() | | copy() | shallow copy | st.copy() |

Subset / superset जाँच

A <= B   # subset
A <  B   # proper subset
A >= B   # superset

Set comprehension और frozenset

squares = {x*x for x in range(5)}   # set comprehension
fs = frozenset([1, 2, 3])           # immutable, hashable set

झटपट जाँच

छोटे अभ्यास

क्या करें और क्या न करें

और गहराई में — complexity की झलक
  • Membership: औसतन ~O(1)
  • Set बीजगणित (|, &, -, ^): O(n)

आम ग़लतियाँ

मुख्य बातें