दिखाई देने वाला तत्व ढूंढेंएक बार
एक सरणी को देखते हुए जहां प्रत्येक तत्व तीन बार होता है, एक तत्व को छोड़कर केवल एक बार होता है। एक बार होता है कि तत्व खोजें।
अपेक्षित समय जटिलता ओ (एन) और ओ (1) अतिरिक्त स्थान है।
उदाहरण:
इनपुट: आगमन [] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
आउटपुट: 2
तो हे (1) अंतरिक्ष की बाधा वहां नहीं थी, आप घटनाओं की गिनती के मूल्यों के साथ हैशपैप के लिए गए थे।
int getUniqueElement(int[] arr)
{
int ones = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" once.
int twos = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" twice.
int not_threes ;
for(int x : arr)
{
twos |= ones & x ; //add it to twos if it exists in ones
ones ^= x ; //if it exists in ones, remove it, otherwise, add it
// Next 3 lines of code just converts the common 1's between "ones" and "twos" to zero.
not_threes = ~(ones & twos) ;//if x is in ones and twos, dont add it to Threes.
ones &= not_threes ;//remove x from ones
twos &= not_threes ;//remove x from twos
}
return ones;
}
असल में, यह तथ्य के उपयोग कि x^x = 0 और 0^x=x बनाता है। तो सभी जोड़े गए तत्व XOR'd प्राप्त करते हैं और अकेला तत्व छोड़कर गायब हो जाते हैं।
संक्षेप में:
थोड़ा लोगों में पहले से ही है, तो यह दुक्की में जोड़ें।
एक्सओआर इस बिट को जोड़ देगा यदि यह वहां नहीं है या अगर यह पहले से मौजूद है तो इसे हटा दें।
यदि थोड़ा और दोनों में दो बिट है, तो इसे एक और दो से हटा दें।
समाप्त होने पर, उनमें से बिट्स केवल 3 * एन + 1 बार दिखाई देते हैं, जो तत्व के लिए बिट्स होते हैं जो केवल एक बार दिखाई देते हैं।
यह सही उत्पादन दे रही है नहीं है, के साथ {1,3,1} –
जैसा कि here वर्णित है, एक सरणी के तत्वों के मध्य में सबसे खराब मामले ओ (एन) समय और ओ (1) अतिरिक्त स्थान में पाया जा सकता है। तो हम विभाजित और जीतने के तरीके के साथ समस्या को हल कर सकते हैं:
ओ (एन) समय में औसत खोजें और तत्वों की संख्या गिनें जो ओ (एन) में औसत से कम या बराबर हैं। यदि यह संख्या 3k + 1 है, तो इसका मतलब है कि उत्तर औसत से कम या बराबर है, इसलिए उन तत्वों को छोड़ दें जो ओ (एन) में औसत से अधिक हैं। अन्यथा, उन लोगों को छोड़ दें जो औसत से कम या बराबर हैं। फिर टी (एन/2) में शेष तत्वों में जवाब मिलते हैं। नोट: शेष तत्वों की संख्या n/2 है क्योंकि हमने तत्वों का आधा हिस्सा छोड़ा है।
तो टी (एन) = टी (एन/2) + ओ (एन) = ओ (एन) और हमें ओ (1) अतिरिक्त स्थान की आवश्यकता है।
मैं mhsekhavat द्वारा प्रस्तावित एक के समान समाधान का प्रस्ताव करता हूं। औसत निर्धारित करने के बजाय, मैं डच राष्ट्रीय ध्वज समस्या http://en.wikipedia.org/wiki/Dutch_national_flag_problem (हां, मैं डच हूं और डिजस्ट्रा की शैली में शिक्षित था) के विभाजन एल्गोरिदम का उपयोग करने का प्रस्ताव करता हूं।
एल्गोरिदम लागू करने का परिणाम एक लाल, सफेद और नीले भाग में विभाजित एक सरणी है। सफेद भाग को पिवट माना जा सकता है। ध्यान दें कि सफेद भाग में पिवट के बराबर सभी तत्व होते हैं, इसलिए सफेद भाग 1 या 3 तत्वों का अस्तित्व में होगा। लाल भाग में पिवट से छोटे तत्व होते हैं और नीले हिस्से में पिवट से बड़े तत्व होते हैं। (ध्यान दें कि लाल और नीले रंग के हिस्सों को क्रमबद्ध नहीं किया जाता है!)
अगला, लाल, सफेद और नीले रंग के हिस्सों के तत्वों की संख्या की गणना करें। यदि किसी भाग में 1 तत्व होता है, तो वह वह संख्या है जिसे आप ढूंढ रहे हैं।अन्यथा, लाल या नीले भाग में केके की एक निर्दिष्ट संख्या के लिए 3k + 1 तत्व होते हैं। उस भाग पर एल्गोरिदम दोहराएं जिसमें 3k + 1 तत्व होते हैं। आखिर में भागों में से एक का आकार 1.
एल्गोरिदम ओ (एन) में चलता है और ओ (1) चर की आवश्यकता होती है।
जावास्क्रिप्ट समाधान:
function findElement(arr) {
var ones = 0;
var twos = 0;
for (var i = 0; i < arr.length; i++) {
ones = (ones^arr[i]) & ~twos;
twos = (twos^arr[i]) & ~ones;
}
return ones;
}
हालांकि सवाल पहले से ही उत्तर है, मैंने पाया अधिक सहज ज्ञान युक्त निम्नलिखित और इसलिए एक जवाब के रूप में जोड़ने। मूल रूप से here
int singleNumber(vector<int>& nums) {
/*Bits in 'ones' are set to 1, when that particular bit
occurs for the first time. Bits in 'twos' are set to 1,
when that particular bit occurs for the second time. If a
bit is occurring for more than 2 times, we throw it away
and start counting again.*/
int ones = 0;
int twos = 0;
for (auto elem : nums) {
int onesOld = ones;
/* (ones^elem): consider the ith bit in 'ones' be 0 (i.e. ith
bit has not occurred till now or has occurred 2 times) and in
'elem' be 1. So, for the ith bit (ones^elem) gives 1. Now,
ith bit could have occurred even number of times as well (i.e.
ith bit in twos is set to 1). If that was the case, we
would like to ignore such bit. This last part is taken care
of by '&' with '~twos'
*/
ones = (ones^elem) & ~twos;
/* (onesOld & elem) gives the bits which have occurred ones
and also occur in this particular element. (twos & ~elem)
gives the bits that have occurred twice and do not occur
in this element. Both these cases take care of the bits
that have occurred 2 times (although a bit might be set
more than 2 times, like 5,7... but we take only modulo 3
count).
*/
twos = (onesOld & elem) | (twos & ~elem);
}
return ones;
}
सुझाव से: उन्हें योग ... – wildplasser