लेटकोड दो योग
मैं वर्तमान में एक अजगर पृष्ठभूमि से सी + + सीख रहा हूं, इसलिए मैं निम्नलिखित समस्या बयान के लिए अजगर और सी ++ में एक समाधान शामिल करूंगा:
पूर्णांक संख्या और पूर्णांक लक्ष्य की एक सरणी को देखते हुए, दो संख्याओं के सूचकांकों को ऐसे लौटाएं कि वे लक्ष्य तक जुड़ जाएं। आप मान सकते हैं कि प्रत्येक इनपुट में एक ही समाधान होगा, और आप एक ही तत्व का दो बार उपयोग नहीं कर सकते हैं। आप किसी भी क्रम में जवाब वापस कर सकते हैं।
उदाहरण 1:
इनपुट: अंक = [2,7,11,15], लक्ष्य = 9
आउटपुट: [0,1]
उदाहरण 2:
इनपुट: अंक = [३,२,४], लक्ष्य = ६
आउटपुट: [1,2]
मैं प्रदर्शन सुधार / अन्य सुझावों के लिए आपकी प्रतिक्रिया / सुझाव सुनना चाहूंगा। यहाँ लिंक है
two_sum.py
def two_sum(nums: list, target: int):
for i, n in enumerate(nums):
match = target - n
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
if __name__ == '__main__':
if result := two_sum([2, 7, 11, 15], 22):
print(f'Indices:\n{result}')
else:
print('No matches found')
Leetcode आँकड़े:
रनटाइम: 772 एमएस, टू सुम के लिए पायथन ऑनलाइन सबमिशन के 36.98% से अधिक तेजी से। मेमोरी उपयोग: 14.4 एमबी, दो सम के लिए पायथन ऑनलाइन सबमिशन के 49.82% से कम।
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
vector<int> two_sum_solution(vector<int> &nums, int target) {
vector <int> results;
for (int i = 0; i < nums.size(); ++i) {
int match = target - nums[i];
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] == match) {
for (int index_match : {
i, j
})
results.push_back(index_match);
}
}
}
return results;
}
#endif //LEETCODE_TWO_SUM_H
main.cpp
#include <vector>
#include "two_sum.h"
using std::vector;
int main() {
vector<int> v1{2, 7, 11, 15};
vector<int> v = two_sum_solution(v1, 22);
if (!v.empty()) {
cout << "Indices:" << endl;
for (auto i: v)
cout << i << " ";
}
else (cout << "No matches found");
}
Leetcode आँकड़े:
रनटाइम: 384 एमएस, टू सुम के लिए सी ++ ऑनलाइन सबमिशन के 34.03% से अधिक तेज। मेमोरी उपयोग: 9.3 एमबी, टू सुम के लिए सी ++ ऑनलाइन सबमिशन के 12.99% से कम।
जवाब
मैं C ++ में विशेषज्ञ नहीं हूं, लेकिन मैं पायथन समाधान के बारे में एक प्रतिक्रिया दे सकता हूं।
आपके मौजूदा समाधान में चलाता है \$O(n^2)\$। मूल रूप से, प्रत्येक संख्या के लिए nइनपुट की nums, लगता है target - nमें nums। इसे कैसे सुधारा जाए?
एल्गोरिथ्म का दूसरा भाग \ से सुधारा जा सकता है$O(n)\$से \ _$O(1)\$। target - nएक सूची में देखने के बजाय , आप एक शब्दकोश का उपयोग कर सकते हैं:
def two_sum(nums: list, target: int):
num_index = {}
for i, n in enumerate(nums):
match = target - n
if match in num_index:
return num_index[match], i
num_index[n] = i
return -1
परिणाम:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
केवल उन हेडर फ़ाइलों को शामिल करें जिनकी आपको आवश्यकता है
आपकी two_sum.hफ़ाइल में, आपको ज़रूरत नहीं है iostream, क्योंकि आप इसकी किसी भी कार्यक्षमता का उपयोग नहीं कर रहे हैं। याद रखें कि #includeवस्तुतः फ़ाइल को कॉपी-पेस्ट करता है, इसलिए यदि आप इस हेडर फ़ाइल को कई फ़ाइलों में शामिल कर रहे हैं, तो यह संभवतः आपके संकलन समय को धीमा कर सकता है।
विभाजन की घोषणाएँ और परिभाषाएँ
आमतौर पर, आप अपनी फ़ाइलों को दो भागों में विभाजित करेंगे: हेडर फ़ाइल (सामान्य रूप से समाप्त *.h, *.hpp, *.hh) और स्रोत फ़ाइल (सामान्य रूप से समाप्त हो रही है *.cpp, *.cc)। हेडर फ़ाइल में केवल घोषणाएँ होती हैं और स्रोत फ़ाइल में कार्यान्वयन होता है।
तो आपके मामले में, आपकी हेडर फ़ाइल इस तरह दिखाई देगी:
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <vector>
std::vector<int> two_sum_solution(std::vector<int> &nums, int target);
#endif // LEETCODE_TWO_SUM_H
और आपकी स्रोत फ़ाइल इस तरह दिखाई देगी:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
वास्तव में, यदि आप अपने two_sum.h(कार्यान्वयन के साथ) कई फाइलों में शामिल करने की कोशिश करते हैं, तो आप वन-डेफिनिशन नियम को तोड़ देंगे । आपकी स्रोत फ़ाइलों में एक ही फ़ंक्शन की कई परिभाषाएँ होंगी, और लिंकर एक त्रुटि को थूक देगा। चारों ओर जाने का एक तरीका कार्यों को चिह्नित करना है inline, लेकिन आप सबसे अधिक संभावना पूर्व को करना चाहते हैं।
कोई using namespaceहेडर फाइल में
using namespaceहेडर फ़ाइल में ऐसा न करें या उसका कोई भी संस्करण न दें। चूंकि शीर्ष लेख फ़ाइल को कई स्रोत फ़ाइलों में चिपकाया जाता है, इसलिए इसमें कष्टप्रद त्रुटियों का कारण होता है। यहाँ देखें
Const संदर्भ का उपयोग करें
चूंकि वेक्टर two_sum_solutionको संशोधित नहीं किया गया numsहै, इसलिए इसे कॉन्स्ट रेफरेंस द्वारा पास करें
सरणी सूचकांकों के लिए size_t बनाम int
सरणी सूचकांकों के लिए int के बजाय size_t का उपयोग करने पर विचार करें
autoज्यादा से ज्यादा इस्तेमाल करें
आपके कोड में कुछ उदाहरण हैं जहां आप autoप्रकार निर्दिष्ट करने के बजाय उपयोग कर सकते हैं । उदाहरण:
auto match = target - nums[i];
auto v = two_sum_solution(v1, 22);
सबसे भीतरी लूप व्यर्थ है
बस करो
results.push_back(i);
results.push_back(j);
इसके अलावा, एक बार समाधान मिल जाने के बाद, आप तुरंत परिणाम वापस करना चाहते हैं।
आप दिए गए सरणी पर पहले पुनरावृति में मूल्य -> सूचकांक का मानचित्र बनाकर प्रदर्शन को बेहतर कर सकते हैं।
वर्तमान में, आपका कार्यक्रम निम्नलिखित (समय जटिलता) करता है:
index, valueसरणी के सभी जोड़ों पर पुनरावृति ( \)$ O(n) \$)- के लिए खोज
target - valueसरणी में ( \$ O(n) \$) target - value( \) का लुकिंग इंडेक्स$ O(n) \$)
और चूंकि ये सभी नेस्टेड हैं, आप \ _$ O(n^2) \$(यह नहीं है \$ n^3 \$ क्योंकि अंतिम पुनरावृत्ति प्रत्येक पुनरावृत्ति के लिए नहीं की जा रही है)।
मेरा प्रस्तावित समाधान:
{value: index}( \) का एक मानचित्र बनाएं$ O(n) \$)index, valueसरणी से अधिक ( \)$ O(n) \$)- नक्शे से लुकअप और रिटर्न इंडेक्स / तानाशाही ( \ _$ O(1) \$)
def two_sum(numbers: list[int], target: int):
lookup: dict = {
value: index
for index, value in enumerate(numbers)
}
for index, value in enumerate(numbers):
match = target - value
if search_index := lookup.get(match):
return index, search_index
return None
यह मेरे लिए दिलचस्प है क्योंकि मैं एक सी पृष्ठभूमि से आता हूं और काम के लिए पिछले कुछ वर्षों से पायथन का उपयोग करना शुरू कर दिया है, इसलिए मैंने आपके साथ रिवर्स पथ प्राप्त किया है। जब मैंने पायथन की शुरुआत की, तो मैंने आपके जैसे समाधानों को बहुत पसंद किया क्योंकि सूचियों के माध्यम से लूपिंग बहुत स्पष्ट और स्पष्ट है।
हालाँकि, मैंने सीखा है कि काम में अधिक कुशल पायथन प्रोग्रामर मेरे कोड को बेहतर तरीके से समझते हैं जब मैं मानक पुस्तकालय का उपयोग करता हूं। एक बार जब मैंने उन उपकरणों को सीखने में निवेश करना शुरू किया, तो उन पर 1 का दोहरा प्रभाव पड़ा) जिससे मेरा कोड अधिक रसीला हो गया और 2) समय और / या अंतरिक्ष में अधिक कुशल हो गया।
इस मामले में, मैं पैकेज combinationsसे समस्या का समाधान करूंगा itertools:
from itertools import combinations
def two_sum(nums, target):
pairs_with_indices = combinations(enumerate(nums), 2)
# result is a generator comprehension.
winning_pairs = ((index_i, index_j)
for (index_i, i), (index_j, j) in pairs_with_indices
if sum((i, j)) == target)
# Insert as much error checking as you need...
return next(winning_pairs)
वहाँ शायद एक और भी बेहतर रसीला और स्पष्ट समाधान Numpy का उपयोग कर रहा है, जो मेरे काम की लाइन (डेटा विज्ञान) में प्रभावी रूप से मानक पुस्तकालय है लेकिन यह हर जगह सच नहीं है।
आपके कोड से भिन्न एक चीज़: ऑफ-बाय-वन-त्रुटियों के लिए कोई जगह नहीं है। मेरे अनुभव में, इस तरह कोड
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
मेरे लिए लिखना आसान है, पढ़ना मुश्किल है और बनाए रखने में मुश्किल से आसान से पूरे जुआ को फैलाया गया है। दूसरे शब्दों में, पायथन में मैन्युअल रूप से सूचकांकों को प्रबंधित करने से मुझे अपने आप को लटकाने के लिए पर्याप्त रस्सी मिलती है, और मानक पुस्तकालय कार्य एक शानदार विकल्प रहा है।
अपने कंटेनरों को जानें
std::unordered_mapइस समस्या में आपका मित्र है। जब भी आपने पहले कभी कोई नंबर नहीं देखा है, बस नंबर और उसके इंडेक्स को जोड़ने के लिए फ़ंक्शन operator[]या insertफ़ंक्शन का उपयोग करें । उपयोग करते समय find, यह एक पुनरावृत्त लौटाएगा, जो एक key-valueजोड़ी है।
उदाहरण के लिए:
auto location = m.find(numToFind);
location->firstआपकी कुंजी है, और
location->secondआपका मूल्य है
जब आप वापस लौटते हैं, तो push_back का उपयोग न करें
आप बस एक प्रारंभिक सूची लौटा सकते हैं जैसे {i,j}:।