एन सॉर्ट किए गए सरणी में कोई अतिरिक्त स्थान

Question

आकार के एन के साथ दिए गए एन सरणी को देखते हुए सामान्य तत्व खोजें, और यदि वे आपको अतिरिक्त स्थान का उपयोग करने की अनुमति नहीं देते हैं, तो उनके सामान्य डेटा को कुशलतापूर्वक या कम समय की जटिलता के साथ कैसे मिलेगा, ?

पूर्व के लिए:

1. 10 160 200 500 500 
2. 4 150 160 170 500 
3. 2 160 200 202 203 
4. 3 150 155 160 300 
5. 3 150 155 160 301 

यह एक साक्षात्कार सवाल यह है कि, मैं कुछ सवाल हैं जिनके समान थे पाया लेकिन वे अतिरिक्त या नहीं इनपुट अनुसार क्रमबद्ध किया जा रहा की शर्तों को शामिल नहीं किया अतिरिक्त स्मृति का उपयोग करने में सक्षम होने।

मैं ओ (एन^2 एलजी एन) जटिलता से कम किसी भी समाधान के बारे में नहीं सोच सकता था। उस मामले में, मैं सबसे सरल समाधान जो मुझे इस जटिलता देता है, जो है के साथ जाने के पसंद करते हैं:

not_found_flag = false 

    for each element 'v' in row-1 
     for each row 'i' in the remaining set 
      perform binary search for 'v' in 'i' 
      if 'v' not found in row 'i' 
       not_found_flag = true 
       break 
     if not not_found_flag 
      print element 'v' as it is one of the common element 

हम मिनट और प्रत्येक पंक्ति की अधिकतम तुलना करके बेहतर बना सकते हैं और उस के आधार पर तय करें कि क्या यह उस पंक्ति के 'min_num' और 'max_num' के बीच होने वाली संख्या 'संख्या' के लिए संभव है।

द्विआधारी खोज -> हे (लॉग एन) n-1 पंक्तियों में खोज 1 संख्या के लिए: पहली पंक्ति ओ (n2logn)

चुने हैं: हे (nlogn) बाइनरी पहली पंक्ति में प्रत्येक संख्या के लिए खोज , हम किसी भी पंक्ति को चुन सकते हैं और यदि किसी भी (एन -1) पंक्तियों में चुनी गई पंक्ति का कोई तत्व नहीं मिलता है तो हमारे पास वास्तव में सामान्य डेटा नहीं है।

Answer 1

ऐसा लगता है कि यह O(n^2) में किया जा सकता है; यानी, बस एक बार प्रत्येक तत्व को देख रहे हैं। ध्यान दें कि यदि सभी तत्वों के लिए एक तत्व आम है तो यह उनमें से किसी एक में मौजूद होना चाहिए। चित्रण के प्रयोजनों के लिए (और चूंकि आपने उपरोक्त लूप का उपयोग किया था) मैं मानता हूं कि हम प्रत्येक सरणी के लिए एक इंडेक्स रख सकते हैं, लेकिन मैं इस बारे में बात करूंगा कि बाद में इसे कैसे प्राप्त किया जाए।

के A_1 के माध्यम से A_N सरणियों कहते हैं, और 1. स्यूडोकोड पर शुरू सूचकांकों का उपयोग करते हैं:

# Initial index values set to first element of each array 
for i = 1 to N: 
    x_i = 1 

for x_1 = 1 to N: 
    val = A_1[x_1] 
    print_val = true 
    for i = 2 to N: 
    while A_i[x_i] < val: 
     x_i = x_i + 1 
    if A_i[x_i] != val: 
     print_val = false 
    if print_val: 
    print val 

एल्गोरिथ्म का स्पष्टीकरण। हम संदर्भ एल्गोरिदम के रूप में पहली सरणी (या किसी भी मनमानी सरणी) का उपयोग करते हैं, और समांतर में अन्य सभी सरणी के माध्यम से पुनरावृत्ति करते हैं (जैसे कि सरणी के प्रकार को छोड़कर मर्ज सॉर्ट के विलय चरण की तरह।) संदर्भ सरणी का प्रत्येक मान यह सभी सरणी के लिए आम है अन्य सभी सरणी में मौजूद होना चाहिए। तो एक दूसरे के सरणी के लिए (जब वे क्रमबद्ध होते हैं), हम सूचकांक x_i बढ़ाते हैं जब तक कि उस सूचकांक A_i[x_i] पर मूल्य कम से कम वह मान नहीं है जिसे हम ढूंढ रहे हैं (हमें कम मूल्यों की परवाह नहीं है; वे आम नहीं हो सकते हैं।) हम यह कर सकते हैं क्योंकि सरणी क्रमबद्ध होती है और इस प्रकार एकान्त रूप से nondecreasing। यदि सभी सरणी के पास यह मान था, तो हम इसे प्रिंट करते हैं, अन्यथा हम संदर्भ सरणी में x_1 बढ़ाते हैं और आगे बढ़ते रहते हैं। हमें यह करना है भले ही हम मूल्य मुद्रित न करें।

अंत में, हमने सभी मानों को आम तौर पर मुद्रित किया है, जबकि केवल सभी तत्वों की जांच की गई है।

अतिरिक्त संग्रहण आवश्यकता के आसपास हो रही है। ऐसा करने के कई तरीके हैं, लेकिन मुझे लगता है कि प्रत्येक सरणी के पहले तत्व को जांचने का सबसे आसान तरीका होगा और संदर्भ सरणी A_1 के रूप में अधिकतम लेना होगा। यदि वे सभी समान हैं, तो उस मान को मुद्रित करें, और उसके बाद इंडेक्स x_2 ... x_N प्रत्येक सरणी के पहले तत्व के रूप में संग्रहीत करें।

जावा कार्यान्वयन (संक्षिप्तता के लिए, अतिरिक्त हैक के बिना), अपने उदाहरण इनपुट का उपयोग:

public static void main(String[] args) { 
    int[][] a = { 
      { 10, 160, 200, 500, 500, }, 
      { 4, 150, 160, 170, 500, }, 
      { 2, 160, 200, 202, 203, }, 
      { 3, 150, 155, 160, 300 }, 
      { 3, 150, 155, 160, 301 } }; 

    int n = a.length; 
    int[] x = new int[n]; 

    for(; x[0] < n; x[0]++) { 
     int val = a[0][x[0]]; 
     boolean print = true; 
     for(int i = 1; i < n; i++) { 
      while (a[i][x[i]] < val && x[i] < n-1) x[i]++;    
      if (a[i][x[i]] != val) print = false;    
     } 
     if (print) System.out.println(val); 
    } 
} 

आउटपुट:

160 

Answer 2

एक O (n^2) (अजगर) है कि नहीं करता है संस्करण अतिरिक्त भंडारण का उपयोग नहीं करते हैं, लेकिन मूल सरणी को संशोधित करें। उन्हें मुद्रण के बिना आम तत्वों स्टोर करने के लिए अनुमति देता है:

data = [ 
    [10, 160, 200, 500, 500], 
    [4, 150, 160, 170, 500], 
    [2, 160, 200, 202, 203], 
    [3, 150, 155, 160, 300], 
    [3, 150, 155, 160, 301], 
] 

for k in xrange(len(data)-1): 
    A, B = data[k], data[k+1] 
    i, j, x = 0, 0, None 

    while i<len(A) or j<len(B): 
     while i<len(A) and (j>=len(B) or A[i] < B[j]): 
      A[i] = x 
      i += 1 

     while j<len(B) and (i>=len(A) or B[j] < A[i]): 
      B[j] = x 
      j += 1 

     if i<len(A) and j<len(B): 
      x = A[i] 
      i += 1 
      j += 1 

print data[-1] 

क्या मैं कर रहा हूँ मूल रूप से डेटा में हर सरणी मिल जाता है और साथ यह बगल में उन है कि आम नहीं हैं को हटाने के तत्व द्वारा तत्व तुलना,,।

Answer 3

यह अजगर O(n^2) में एक समाधान है, बिना किसी अतिरिक्त स्थान का उपयोग करता है, लेकिन सूचियों को नष्ट कर देता:

def find_common(lists): 
    num_lists = len(lists) 
    first_list = lists[0] 
    for j in first_list[::-1]: 
     common_found = True 
     for i in range(1,num_lists): 
      curr_list = lists[i] 
      while curr_list[len(curr_list)-1] > j: 
       curr_list.pop() 
      if curr_list[len(curr_list)-1] != j: 
       common_found = False 
       break 
     if common_found: 
      return j 

Answer 4

यहाँ जावा कार्यान्वयन

public static Integer[] commonElementsInNSortedArrays(int[][] arrays) { 
    int baseIndex = 0, currentIndex = 0, totalMatchFound= 0; 
    int[] indices = new int[arrays.length - 1]; 
    boolean smallestArrayTraversed = false; 
    List<Integer> result = new ArrayList<Integer>(); 
    while (!smallestArrayTraversed && baseIndex < arrays[0].length) { 
     totalMatchFound = 0; 
     for (int array = 1; array < arrays.length; array++) { 
      currentIndex = indices[array - 1]; 
      while (currentIndex < arrays[array].length && arrays[array][currentIndex] < arrays[0][baseIndex]) { 
       currentIndex ++;      
      } 

      if (currentIndex < arrays[array].length) { 
       if (arrays[array][currentIndex] == arrays[0][baseIndex]) { 
        totalMatchFound++; 
       } 
      } else { 
       smallestArrayTraversed = true; 
      } 
      indices[array - 1] = currentIndex; 
     } 
     if (totalMatchFound == arrays.length - 1) { 
      result.add(arrays[0][baseIndex]); 
     } 
     baseIndex++; 
    } 

    return result.toArray(new Integer[0]); 
} 

यहाँ यूनिट टेस्ट है

@Test 
public void commonElementsInNSortedArrayTest() { 
    int arr[][] = { {1, 5, 10, 20, 40, 80}, 
        {6, 7, 20, 80, 100}, 
        {3, 4, 15, 20, 30, 70, 80, 120} 
        }; 

    Integer result[] = ArrayUtils.commonElementsInNSortedArrays(arr); 
    assertThat(result, equalTo(new Integer[]{20, 80})); 

    arr = new int[][]{ 
      {23, 34, 67, 89, 123, 566, 1000}, 
      {11, 22, 23, 24,33, 37, 185, 566, 987, 1223, 1234}, 
      {23, 43, 67, 98, 566, 678}, 
      {1, 4, 5, 23, 34, 76, 87, 132, 566, 665}, 
      {1, 2, 3, 23, 24, 344, 566} 
      }; 

    result = ArrayUtils.commonElementsInNSortedArrays(arr); 
    assertThat(result, equalTo(new Integer[]{23, 566})); 
} 

है