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)

आम ग़लतियाँ

मुख्य बातें