العثور على رقم واحد في القائمة [نسخة مكررة]

Question

هذا السؤال لديه بالفعل إجابة هنا:

• كيفية العثور على الرقم الوحيد في المصفوفة الذي لا يتكرر مرتين [نسخة مكررة] 5 إجابات

ما هي أفضل خوارزمية للعثور على رقم يحدث مرة واحدة فقط في القائمة التي تحتوي على جميع الأرقام الأخرى التي تحدث مرتين بالضبط.

لذا، في قائمة الأعداد الصحيحة (لنأخذها كمصفوفة) يتكرر كل عدد صحيح مرتين بالضبط، باستثناء واحد.للعثور على ذلك، ما هي أفضل خوارزمية.

Answer 1

الطريقة الأسرع (O(n)) والأكثر كفاءة في الذاكرة (O(1)) هي عملية XOR.

شركة:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

يؤدي هذا إلى طباعة "1"، وهو الرقم الوحيد الذي يحدث مرة واحدة.

ينجح هذا لأنه في المرة الأولى التي تضغط فيها على رقم، فإنه يحدد المتغير num مع نفسه، وفي المرة الثانية يقوم بإلغاء تحديد num مع نفسه (أكثر أو أقل).الشيء الوحيد الذي يبقى بدون علامة هو ملفك غير المكرر.

Answer 2

بالمناسبة، يمكنك التوسع في هذه الفكرة للعثور بسرعة كبيرة اثنين أرقام فريدة من بين قائمة التكرارات.

دعونا نسمي الأرقام الفريدة a و b.أولاً، خذ XOR لكل شيء، كما اقترح كايل.ما نحصل عليه هو أ ^ ب.نحن نعلم أن a^b != 0، حيث أن a != b.اختر أي بت واحد من a^b، واستخدمه كقناع - بمزيد من التفاصيل:اختر x كقوة للرقم 2 بحيث تكون x & (a^b) غير صفرية.

الآن قم بتقسيم القائمة إلى قائمتين فرعيتين - تحتوي إحدى القائمة الفرعية على جميع الأرقام y مع y&x == 0، والباقي يذهب إلى القائمة الفرعية الأخرى.بالمناسبة، اخترنا x، ونحن نعلم أن a وb موجودان في مجموعات مختلفة.ونعلم أيضًا أن كل زوج من التكرارات لا يزال في نفس المجموعة.لذلك يمكننا الآن تطبيق خدعة "XOR-em-all" القديمة على كل مجموعة بشكل مستقل، واكتشاف ماهية a وb بالكامل.

بام.

Answer 3

O(N) الوقت، O(N) الذاكرة

HT = جدول التجزئة

ht.clear () انتقل إلى القائمة من أجل كل عنصر تراه

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

في النهاية، العنصر الموجود في HT هو العنصر الذي تبحث عنه.

ملاحظة (الائتمان @ جاريد أبدايك):سيجد هذا النظام جميع المثيلات الفردية للعناصر.

---

تعليق:لا أرى كيف يمكن للأشخاص التصويت على الحلول التي تمنحك أداء NLogN.في أي عالم هذا "الأفضل"؟لقد شعرت بصدمة أكبر لأنك حددت حل NLogN للإجابة المقبولة ...

ومع ذلك، أوافق على أنه إذا كان المطلوب أن تكون الذاكرة ثابتة، فسيكون NLogN هو الحل الأفضل (حتى الآن).

Answer 4

من الواضح أن حل كايل لن يلتقط المواقف إذا كانت مجموعة البيانات لا تتبع القواعد.إذا كانت جميع الأرقام في أزواج، فستعطي الخوارزمية نتيجة صفر، وهي نفس القيمة تمامًا كما لو كان الصفر هو القيمة الوحيدة ذات التكرار الفردي.

إذا كان هناك عدة قيم مفردة أو ثلاثية، فستكون النتيجة خطأً أيضًا.

قد يؤدي اختبار مجموعة البيانات إلى استخدام خوارزمية أكثر تكلفة، سواء من حيث الذاكرة أو الوقت.

يُظهر حل Csmba بعض بيانات الخطأ (لا يوجد أو أكثر من قيمة حدوث واحدة)، ولكن ليس غيرها (الرباعيات).فيما يتعلق بالحل الذي توصل إليه، اعتمادًا على تنفيذ HT، فإن الذاكرة و/أو الوقت أكبر من O(n).

إذا لم نتمكن من التأكد من صحة مجموعة الإدخال، فإن الفرز والعد أو استخدام حالات العد القابلة للتجزئة مع كون العدد الصحيح نفسه هو مفتاح التجزئة سيكون ممكنًا.

Answer 5

أود أن أقول إن استخدام خوارزمية الفرز ثم تصفح القائمة المصنفة للعثور على الرقم يعد طريقة جيدة للقيام بذلك.

والآن تكمن المشكلة في العثور على خوارزمية الفرز "الأفضل".هناك الكثير من خوارزميات الفرز، ولكل منها نقاط القوة والضعف الخاصة بها، لذلك هذا سؤال معقد للغاية.ال دخول ويكيبيديا يبدو وكأنه مصدر جيد للمعلومات حول ذلك.

Answer 6

التنفيذ في روبي:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

Answer 7

يتعين عليك تحديد ما تعنيه بكلمة "الأفضل" - بالنسبة للبعض، السرعة هي كل ما يهم وستؤهل الإجابة على أنها "الأفضل" - بالنسبة للآخرين، قد يسامحون بضع مئات من المللي ثانية إذا كان الحل أكثر قابلية للقراءة.

"الأفضل" هو أمر شخصي إلا إذا كنت أكثر تحديدًا.

---

هكذا قال:

قم بالتكرار عبر الأرقام، لكل رقم ابحث في القائمة عن هذا الرقم وعندما تصل إلى الرقم الذي يُرجع 1 فقط لعدد نتائج البحث، تكون قد انتهيت.

Answer 8

يبدو أن أفضل ما يمكنك فعله هو التكرار خلال القائمة، فكل عنصر أضفه إلى قائمة العناصر "المرئية" أو قم بإزالته من "المرئية" إذا كان موجودًا بالفعل، وفي النهاية قائمة العناصر "المرئية" "ستتضمن العناصر العنصر المفرد.هذا هو O(n) فيما يتعلق بالوقت وn فيما يتعلق بالمكان (في أسوأ الحالات، سيكون أفضل بكثير إذا تم فرز القائمة).

حقيقة أنها أعداد صحيحة لا تؤثر حقًا، لأنه لا يوجد شيء مميز يمكنك القيام به عند جمعها...هل هناك؟

سؤال

لا أفهم سبب كون الإجابة المحددة هي "الأفضل" بأي معيار.O(N*lgN) > O(N)، ويقوم بتغيير القائمة (أو إنشاء نسخة منها، والتي لا تزال أكثر تكلفة في المكان والزمان).هل فاتني شيء؟

Answer 9

يعتمد ذلك على مدى كبر/صغر/تنوع الأرقام.قد يكون الفرز الجذري قابلاً للتطبيق مما يقلل من وقت الفرز لحل O(N log N) بدرجة كبيرة.

Answer 10

أسلوب الفرز وأسلوب XOR لهما نفس التعقيد الزمني.تكون طريقة XOR هي O(n) فقط إذا افترضت أن XOR لسلسلتين هي عملية زمنية ثابتة.وهذا يعادل القول بأن حجم الأعداد الصحيحة في المصفوفة يحده ثابت.في هذه الحالة، يمكنك استخدام فرز Radix لفرز المصفوفة في O(n).

إذا كانت الأرقام غير محدودة، فإن XOR للبت يستغرق وقتًا O(k) حيث k هو طول سلسلة البتات، وتأخذ طريقة XOR O(nk).الآن مرة أخرى، سيقوم الفرز الجذري بفرز المصفوفة في الوقت المناسب O(nk).

Answer 11

يمكنك ببساطة وضع العناصر الموجودة في المجموعة في تجزئة حتى تجد تصادمًا.في روبي، هذه بطانة واحدة.

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

لذا، find_dupe([1,2,3,4,5,1]) سيعود 1.

هذا في الواقع سؤال "خدعة" شائع في المقابلة.يتعلق الأمر عادةً بقائمة من الأعداد الصحيحة المتتالية مع نسخة واحدة مكررة.في هذه الحالة، غالبًا ما يبحث القائم بالمقابلة عنك لاستخدام المجموع الغوسي ن-خدعة الأعداد الصحيحة على سبيل المثال. n*(n+1)/2 مطروحًا من المبلغ الفعلي.إجابة الكتاب المدرسي هي شيء من هذا القبيل.

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end