पूर्णांक की एक 2-डी ऐरे छंटनी जिनकी पंक्तियां और कॉलम तत्व क्रमबद्ध हैं

Question

मुझे बस थोड़ी मदद चाहिए। मैं एक काम जहाँ मैं एक कुशल मार्ग आवश्यकता कर रहा हूँ क्रमबद्ध करने के लिए 2-डी पूर्णांक सरणी जिनमें से पंक्ति और स्तंभ तत्वों पहले से ही आरोही क्रम। (बेहतर भाषा C/C++) में हल कर रहे हैं।

इनपुट:

1 5 10 15 20 
2 7 12 17 22 
4 9 18 25 28 
11 14 21 26 31 

आउटपुट:

1 2 4 5 7 
9 10 11 12 14 
15 17 18 20 21 
22 25 26 28 31 

अग्रिम धन्यवाद।

Answer 1

यहां एक संकेत है - यह मानते हुए कि सामान्य 2 डी सी सरणी है, टाइपकास्टिंग का थोड़ा सा उपयोग करके, आप इसे 1 डी सरणी के रूप में समझने में सक्षम होना चाहिए।

Answer 2

विलय विधि (या पंक्तियों) को विलय विधि का उपयोग करके मर्ज विधि का उपयोग करके मर्ज करें।

इससे इस तथ्य का लाभ उठाया जाएगा कि प्रत्येक कॉलम स्वयं ही क्रमबद्ध है।

यह पर्याप्त तेज़ होना चाहिए।

संपादित

और ऐसा लगता है किसी मर्ज समारोह पहले से ही मानक पुस्तकालय में नहीं है। http://en.cppreference.com/w/cpp/algorithm/merge

Answer 3

मैं कुछ प्रकार के एल्गोरिदम का उपयोग "बाढ़ भरने" या पथ खोजने वाले एल्गोरिदम जैसे * * के समान करता हूं। ऊपरी बाएं कोने (मान 1) में शुरू करें, इसे आउटपुट करें और दाएं और नीचे तक "विस्तृत करें" - इसलिए अपनी मान (2 और 5) को एक सूची में जोड़ें। वे दोनों 1 से अधिक होंगे। अब अपनी सूची (मूल्य 2) से सबसे छोटा मूल्य आउटपुट करें और इसे "विस्तृत करें" भी करें। आपको अपनी सूची में 4 और 7 जोड़ा जाएगा, आउटपुट 4 और "इसे विस्तारित करें", और इसी तरह।

ध्यान दें कि सूची को क्रमबद्ध करके, आप तुरंत सबसे छोटे तत्व को आउटपुट कर सकते हैं और एक बार में लगातार मूल्यों के कई "रन" आउटपुट करने में भी सक्षम हो सकते हैं (f.e. 10,11,12)। तो छद्म कोड होगा:

// array a[y][x] 
// list L - ordered insertion, additionally stores matrix indices of values 
add a[0][0] to L 
loop until L is empty 
    output first element of L 
    remove first element of L and add its right and bottom neighbors (if any) to L 
loop end 

संपादित करें: यहां एक कामकाजी सी कार्यान्वयन है।

#include <stdio.h> 
#include <stdlib.h> 

#define COLS 5 
#define ROWS 4 

int matrix[ROWS][COLS] = { 
    1, 5, 10, 15, 20, 
    2, 7, 12, 17, 22, 
    4, 9, 18, 25, 28, 
    11, 14, 21, 26, 31 
}; 

struct entry { 
    int value; 
    int x, y; 
}; 

entry list[ROWS+COLS]; // Not sure how big the list can get, but this should be enough 
int list_len = 0; 

void set_list_entry(int index, int value, int x, int y) { 
    list[index].value = value; 
    list[index].x = x; 
    list[index].y = y; 
} 

void add_to_list(int x, int y) { 
    int val = matrix[y][x]; 
    int i, pos = list_len; 

    for (i = 0; i < list_len; i++) { 
    if (list[i].value == val) return; // Don't add value that is on the list already 
    if (list[i].value > val) { 
     pos = i; 
     break; 
    } 
    } 
    // Shift the elements after pos 
    for (i = list_len + 1; i > pos; i--) { 
    set_list_entry(i, list[i - 1].value, list[i - 1].x, list[i - 1].y); 
    } 
    // Insert new entry 
    set_list_entry(pos, val, x, y); 

    list_len++; 
} 

int main() { 
    int iteration = 0; 

    add_to_list(0,0); 

    do { 
    // output first element of list 
    printf("%i ", list[0].value); 
    iteration++; 
    if ((iteration % COLS) == 0) printf("\n"); 
    // add neighbors of first element of list to the list 
    if (list[0].x < (COLS - 1)) add_to_list(list[0].x + 1, list[0].y); 
    if (list[0].y < (ROWS - 1)) add_to_list(list[0].x, list[0].y + 1); 
    // remove first element of list 
    for (int i = 0; i < list_len; i++) { 
     set_list_entry(i, list[i + 1].value, list[i + 1].x, list[i + 1].y); 
    } 
    list_len--; 
    } while (list_len > 0); 

    return 0; 
} 

सूची की लंबाई के बारे में टिप्पणी नोट करें। मुझे यकीन है कि कितना बड़ा सूची प्राप्त कर सकते हैं नहीं कर रहा हूँ, लेकिन मुझे लगता COLS+ROWS पर्याप्त इस सबसे खराब स्थिति को देखकर किया जाना चाहिए:

1 3 5 7 9 .. 
2 y y y y 
4 y x x x 
6 y x x x 
8 y x x x 
. 
. 

सभी "सीमा" तत्वों छोटी से छोटी y मूल्य से कम हैं, तो आप मिल जाएगा प्रक्रिया में y मानों से भरा एक सूची, जो (ROWS - 1) + (COLS - 1) तत्वों का लंबा है।

ऐसे सबसे खराब मामलों को देखते हुए, मुझे लगता है कि यह सबसे कुशल समाधान नहीं है, लेकिन मुझे लगता है कि यह एक सुरुचिपूर्ण और संक्षिप्त है।

Answer 4

हम इस सवाल को क्यों नहीं मानते हैं कि "एन सॉर्टेड सूची में विलय करने के प्रत्येक के पास तत्व हैं"।

के तत्व का एक न्यूनतम ढेर बनाना। उस न्यूनतम ढेर में क्रमबद्ध सूची के प्रत्येक सबसे छोटे तत्व को डालना। ढेर की जड़ें पॉपिंग। अब सूची का अगला तत्व डालें जिसका तत्व रूट था। इस तरह हम एन * के लॉग (के) की जटिलता प्राप्त करते हैं।

उपरोक्त मामले में यह एन^2log (एन) होगा, जहां एन एक पंक्ति में तत्व की संख्या है।