6
में डुप्लिकेट पंक्तियों की जांच करने के लिए कुशल एल्गोरिदम पूर्णांक के मैट्रिक्स एम को देखते हुए। जांचें कि मैट्रिक्स में दो पंक्तियां समान हैं या नहीं। इष्टतम दृष्टिकोण दें।मैट्रिक्स
Example:
[{1, 2, 3},
{3, 4, 5},
{1, 2, 3}]
उपरोक्त मैट्रिक्स में, पंक्तियां 1 और 3 समान हैं।
संभव समाधान:
Given a matrix, we can convert each row in a string (example using to_string()
method of C++ and concatenating each element in a row to a string). We do this
for every row of the matrix, and insert it in a table that is something like
(map<string, int> in C++). And hence, duplicate row can be checked in O(mn) time
for an mxn matrix.
मैं इससे बेहतर कर सकते हैं? या, उपर्युक्त विधि में कोई दोष है?
मुझे उम्मीद नहीं है कि आप ओ (एमएन) से बेहतर कर सकते हैं क्योंकि सबसे खराब मामले में प्रत्येक तत्व को पढ़ने की आवश्यकता होगी। – Matt
यह कारण होगा कि @Matt ने कहा था। बस एक चेतावनी, जब आप तत्वों को जोड़ते हैं तो आपको कुछ डिलीमीटर लगाने की आवश्यकता होती है। अन्यथा '{1, 23}' और '{12, 3} 'को वही माना जाएगा। – justhalf
@justhalf: इसे इंगित करने के लिए धन्यवाद। –