एक सरणी

Question

में दो बार नहीं होने वाला पूर्णांक खोजें: मैं इस समस्या को हल करने का प्रयास कर रहा हूं: एक पूर्णांक सरणी में सभी संख्याएं ठीक से दो बार होती हैं, एक ही संख्या को छोड़कर जो बिल्कुल ठीक होती है।

एक सरल समाधान सरणी को सॉर्ट करना है और फिर गैर पुनरावृत्ति के लिए परीक्षण करना है। लेकिन मैं बेहतर समाधान की तलाश में हूं जिसमें ओ (एन) की समय जटिलता है।

Answer 1

आप संपूर्ण सरणी पर "xor" ऑपरेशन का उपयोग कर सकते हैं। संख्याओं की प्रत्येक जोड़ी एक दूसरे को रद्द कर देगी, जिससे आपको मांगे गए मूल्य के साथ छोड़ दिया जाएगा।

int get_orphan(int const * a, int len) 
{ 
    int value = 0; 
    for (int i = 0; i < len; ++i) 
     value ^= a[i]; 

    // `value` now contains the number that occurred odd number of times. 
    // Retrieve its index in the array. 
    for (int i = 0; i < len; ++i) 
    { 
     if (a[i] == value) 
      return i; 
    } 

    return -1; 
}