सूची में सबसे कम अप्रयुक्त अद्वितीय आईडी ढूंढना

Question

कहें कि एक सूची है। सूची में प्रत्येक आइटम में एक अद्वितीय आईडी है।

List [5, 2, 4, 3, 1] 

जब मैं इस सूची से कोई आइटम हटाता हूं, तो आइटम से अद्वितीय आईडी इसके साथ जाती है।

List [5, 2, 3, 1] 

अब कहें कि मैं सूची में एक और आइटम जोड़ना चाहता हूं, और इसे सबसे कम न्यूनतम अद्वितीय आईडी देना चाहता हूं।

सूची में कोई नया आइटम जोड़ते समय सबसे कम अद्वितीय आईडी प्राप्त करने का सबसे आसान तरीका क्या है?

यहां प्रतिबंध है हालांकि: अगर मैं किसी आइटम को हटाते समय किसी अन्य आइटम की अनूठी आईडी को पुन: असाइन नहीं करता तो मैं इसे पसंद करूंगा।

मुझे एहसास है कि अद्वितीय आईडी को ढूंढना आसान होगा यदि मैंने अनन्य आईडी 5 को अनन्य आईडी 4 को दोबारा हटा दिया 4। फिर मुझे सूची की लंबाई (5) मिल सकती है और अद्वितीय आइटम के साथ नया आइटम बना सकता है उस नंबर के साथ आईडी।

तो क्या कोई और तरीका है, जिसमें पूरी सूची के माध्यम से पुनरावृत्ति शामिल नहीं है?

संपादित करें:

भाषा जावा है, लेकिन मुझे लगता है मैं एक सामान्य एल्गोरिथ्म के लिए देख रहा हूँ लगता है।

Answer 1

एक आसान तेज़ तरीका है कि आप अपने हटाए गए आईडी को प्राथमिकता कतार में डालें, और जब आप नए डालें (या कतार के बाद पहली सूची के आकार() + 1 का उपयोग करें तो वहां से अगली आईडी चुनें खाली है)। हालांकि इसे एक और सूची की आवश्यकता होगी।

Answer 2

इसकी खोज के बराबर है, इस बार जब आप एक गुम संख्या की खोज करते हैं। यदि आपकी आईडी को पूर्णांक क्रमबद्ध किया गया है, तो आप दो आईडी के बीच की जगह 1. यदि आप जानते हैं कि सूची में कितने आइटम हैं और इसके क्रमबद्ध हैं, तो आप बाइनरी खोज को कार्यान्वित कर सकते हैं।

Answer 3

मुझे नहीं लगता कि आप सूची के माध्यम से इसे बिना किए बिना कर सकते हैं।

जब आप कहते हैं कि

'अब कहते हैं कि मैं सूची लिए अन्य आइटम जोड़ने, और यह कम से कम उच्चतम विशिष्ट आईडी देना चाहते हैं। '

मुझे लगता है कि आप का मतलब है कि आप सबसे कम उपलब्ध आईडी असाइन करना चाहते हैं जिसका उपयोग कहीं और नहीं किया गया है।

आप ऐसा कर सकते हैं:

private int GetLowestFreeID(List list){ 
    for (int idx = 0; idx < list.Length; ++i){ 
     if (list[idx] == idx) continue; 
     else return idx; 
    } 
} 

इस सबसे कम मुक्त सूचकांक देता है।

यह मानता है कि आपकी सूची क्रमबद्ध है, और सी # में है लेकिन आपको विचार मिलता है।

Answer 4

आप उपलब्ध आईडी की एक सूची बनाए रख सकते हैं।

boolean register[3]; 
register[0] = false; 
register[1] = false; 
register[2] = false; 

जब आप एक false मूल्य जब तक एक तत्व, रजिस्टर के नीचे से पाश जोड़ने पाया जाता है:

एक बूलियन सरणी (छद्म कोड) घोषित। गलत मान को सत्य पर सेट करें, उस इंडेक्स को अद्वितीय पहचानकर्ता के रूप में असाइन करें।

removeObject(index) 
{ 
    register[index] = false; 
} 

getsetLowestIndex() 
{ 
    for(i=0; i<register.size;i++) 
    { 
     if(register[i]==false) 
     { 
      register[i] = true; 
      return i; 
     } 
    } 

    // Array is full, increment register size 
    register.size = register.size + 1; 
    register[register.size] = true; 
    return register.size; 
} 

जब आप कोई तत्व हटाते हैं, तो बस सूचकांक को गलत पर सेट करें।

आप निरंतरता मार्कर रखने के द्वारा इसे बड़ी सूचियों के लिए अनुकूलित कर सकते हैं ताकि आपको पूरी चीज़ को लूप करने की आवश्यकता न हो।

यह आपके उदाहरण के लिए सबसे अच्छा काम करेगा जहां इंडेक्स किसी विशेष क्रम में नहीं हैं, इसलिए आप उन्हें पहले क्रमबद्ध करने की आवश्यकता को छोड़ देते हैं।

Answer 5

डेटा संरचना जो ऐसा करने के लिए उपयोग की जाएगी वह प्राथमिकता बाइनरी हीप है जो केवल अद्वितीय मानों की अनुमति देती है।

Answer 6

सूची को क्रमबद्ध रखने के बारे में कैसे। और आप इसे आसानी से एक छोर से हटा सकते हैं।