रैखिक समय में सरणी से डुप्लिकेट निकालें और अतिरिक्त सरणी के बिना

Question

हमारे पास एक सरणी है और यह निरस्त नहीं है। हम जानते हैं कि सीमा [0, एन] है।

हम डुप्लिकेट निकालना चाहते हैं, लेकिन हम अतिरिक्त सरणियों उपयोग नहीं कर सकते और यह चाहिए रैखिक समय में रन।

कोई विचार? बस स्पष्ट करने के लिए, यह होमवर्क के लिए नहीं है!

Answer 1

यदि पूर्णांक 0 से n तक सीमित हैं, तो आप सरणी के माध्यम से स्थानांतरित कर सकते हैं, संख्याओं को उनके सूचकांक द्वारा रख सकते हैं। प्रत्येक बार जब आप किसी नंबर को प्रतिस्थापित करते हैं, तो वह मान लें जो वहां होता था और इसे स्थानांतरित करने के लिए कहां जाना चाहिए। उदाहरण के लिए, मान लीजिए कि हम आकार 8 की एक सरणी डालते हैं:

----------------- 
|3|6|3|4|5|1|7|7| 
----------------- 
S 

कहाँ एस हमारे प्रारंभिक बिंदु है, और हम सी का उपयोग अपने "वर्तमान" नीचे सूचकांक का ट्रैक रखने के। हम इंडेक्स 0 के साथ शुरू करते हैं, और 3 इंडेक्स स्पॉट पर 3 ले जाते हैं, जहां 4 है। एक temp var में 4 सहेजें।

----------------- 
|X|6|3|3|5|1|7|7| Saved 4 
----------------- 
S  C 

हम तो सूचकांक 4 में 4 शब्दों में कहें, बचत वहाँ क्या हुआ करता था, 5.

----------------- 
|X|6|3|3|4|1|7|7| Saved 5 
----------------- 
S  C 

----------------- 
|X|6|3|3|4|5|7|7| Saved 1 
----------------- 
S   C 

----------------- 
|X|1|3|3|4|5|7|7| Saved 6 
----------------- 
S C 

----------------- 
|X|1|3|3|4|5|6|7| Saved 7  
----------------- 
S   C 

जारी रखें जब हम 7 को बदलने के लिए प्रयास करते हैं, हम देखते हैं एक संघर्ष, तो हम बस इसे जगह नहीं है। हम तो शुरू सूचकांक S से जारी रखने के लिए, 1 से यह भी वृद्धि:

----------------- 
|X|1|3|3|4|5|6|7| 
----------------- 
    S   

1 यहाँ ठीक है, 3 की जरूरत है स्थानांतरित करने के लिए

----------------- 
|X|1|X|3|4|5|6|7| 
----------------- 
    S 

लेकिन 3 डुप्लिकेट है, तो हम इसे फेंक और रख बाकी सरणी के माध्यम से पुनरावृत्ति।

तो मूल रूप से, हम प्रत्येक प्रविष्टि को अधिकतम 1 बार स्थानांतरित करते हैं, और पूरे सरणी के माध्यम से फिर से चलाते हैं। वह ओ (2 एन) = ओ (एन)

Answer 2

क्या आप सॉर्ट कर सकते हैं? रेडिक्स सॉर्ट के साथ क्रमबद्ध करें - http://en.wikipedia.org/wiki/Radix_sort दिए गए मामले के लिए जटिलता ओ (सरणीकरण) के साथ और फिर क्रमबद्ध सरणी ओ (सरणी आकार) से डुप्लिकेट हटा दें।

Answer 3

मान लें int a[n] श्रेणी [0, एन -1] में पूर्णांक की एक सरणी है। ध्यान दें कि यह बताई गई समस्या से थोड़ा अलग है, लेकिन मैं यह धारणा स्पष्ट करता हूं कि एल्गोरिदम कैसे काम करता है। श्रेणी [0, एन] में पूर्णांक के लिए काम करने के लिए एल्गोरिदम को पैच किया जा सकता है।

for (int i=0; i<n; i++) 
{ 
    if (a[i] != i) 
    { 
     j = a[i]; 
     k = a[j]; 
     a[j] = j; // Swap a[j] and a[i] 
     a[i] = k; 
    } 
} 

for (int i=0; i<n; i++) 
{ 
    if (a[i] == i) 
    { 
     printf("%d\n", i); 
    } 
} 

Answer 4

void printRepeating(int arr[], int size) 
{ 
    int i; 
    printf("The repeating elements are: \n"); 
    for(i = 0; i < size; i++) 
    { 
    if(arr[abs(arr[i])] >= 0) 
     arr[abs(arr[i])] = -arr[abs(arr[i])]; 
    else 
     printf(" %d ", abs(arr[i])); 
    } 
} 

Answer 5

सरणी के माध्यम से वॉक सरणी [सरणी [i]] = -array आवंटित [सरणी [i]]; अगर नकारात्मक नहीं है; यदि यह पहले से ही ऋणात्मक है तो इसका डुप्लिकेट, यह काम करेगा क्योंकि सभी मान 0 और एन के भीतर हैं।

Answer 6

पूरा करने के लिए @ जोएल ली का कोड विस्तारित करना।

#include <iostream> 
void remove_duplicates(int *a, int size) 
{ 
    int i, j, k; 
    bool swap = true; 

    while(swap){ 
    swap = false; 
    for (i=0; i<size; i++){ 
     if(a[i] != i && a[i] != a[a[i]]){ 
      j = a[i]; 
      k = a[j]; 
      a[i] = k; 
      a[j] = j; 
      swap = true;  
     } 

    } 
    } 
} 

int main() 
{ 
    int i; 
    //int array[8] = {3,6,3,4,5,1,7,7}; 
    int array[8] = {7,4,6,3,5,4,6,2}; 

    remove_duplicates(array, sizeof(array)/sizeof(int)); 

    for (int i=0; i<8; i++) 
     if(array[i] == i) 
      std::cout << array[i] << " "; 

    return 0; 
}