الاستخدام الذكي لمشغل XOR للعثور على الرقم المفقود

Question

لقد صادفت المشكلة التالية على Leetcode وحاولت حلها مع التعليمة البرمجية التالية ومع ذلك، يبدو أن هناك حل أفضل يستفيد من XOR.يحتوي LeetCode على وصف لحل XOR ولكن لا يمكنني فهمه بالكامل.

لا أستطيع أن ألتف رأسي حول سبب نحتاج إلى تهيئة المتغير المفقود مع طول الصفيف، لماذا لا تهيئة الأمر مع صفر ومتى نفعله مع الصفر، لماذا لا تستطيعهذا الاجائن يجد الرقم المفقود؟يمكن للشخص يرجى توضيح ذلك؟

href="https://i.stack.imgur.com/tsuf8.png" er="nofollow noreferrer">

التالية كان حلاي قبل أن تعلمت Leetcode أن حل XOR المقترح هو أفضل وأسرع

giveacodicetagpre.

Answer 1

دعونا نستخدم مثال أبسط للتحقق من الحقيقة.

لنفترض $ n= 1 $ ، أي نحن، نحن نعطي مجموعة تحتوي على رقم واحد (متميز) مأخوذ من 0، 1.

• إذا كان الرقم المحدد هو 0، فيجب أن يكون الرقم المفقود $ 1= 1 \ Land0 $ .
• إذا كان الرقم المحدد هو 1، فيجب أن يكون الرقم المفقود $ 0= 1 \ Land1 $ .

لتلخيص، إذا كان الرقم المحدد هو $ $ ، ثم الرقم المفقود هو $ 1 \ Land a= n \ Land a \ or= 0 \ land a $ .

---

ما هي الأسباب الأساسية وراء هذا السحر في المواقف العامة؟

اتضح مشغل xor bitwise، يشار إليه عادة بواسطة " $ \ Land $ " في لغات البرمجة، يتصرف مثل مشغل Plus العادي.

• هو التخفيف و Associative . لذلك لا يهم ترتيب العمليات على الإطلاق.
• $ 0 $ وظائف الوظائف مثل الصفر، أي $ a \ land 0= a $ . لذا $ 0 $ يمكن إزالتها.
• $ a \ land a= 0 $ لكل رقم $ $ . لذلك إذا ظهر نفس الرقم مرتين، فإنها تلغي بعضها البعض.

خارج لغات البرمجة، فإن XOR bitwise هو أكثر شيوعا كما هو " $ \ Oplus $ "، حيث رمز زائد، " $ + $ " في الوسط يذكرنا أنه يتصرف مثل الإضافة العادية.

الآن فكر في التعبير، $$ (0 \ Oplus1 \ Oplus2 \ oplus3 \ oplus3 \ cdots \ oplus n) \ oplus (a_0 \ oplus a_1 \ oplus a_2 \ cdots \ oplus a_ _ { n-1}). $ كلما كان هناك زوج من نفس العدد، يمكننا إزالتها. لذلك يتم إلغاء جميع الأرقام بين بعضها البعض، باستثناء هذا الرقم المفقود، لأن هذا الرقم المفقود هو الرقم الوحيد الذي يظهر في $$ 0 \ Oplus1 \ Oplus2 \ Oplus3 \ cdots \ Oplus N $ $ ولكن ليس في $$ a_0 \ oplus a_1 \ oplus a_2 \ cdots \ oplus a_ {n-1}. $$ so،

$$ (0 \ Oplus1 \ Oplus2 \ oplus3 \ oplus3 \ cdots \ oplus n) \ oplus (a_0 \ oplus a_1 \ oplus a_2 \ cdots \ oplus a_ {n-1})=text {الرقم المفقود} $

دعونا نغير ترتيب "التلخيص" على الجانب الأيسر. يمكننا إقران $ 0 $ مع $ a_0 $ ، $ 1 $ مع $ a_1 $ ، $ 2 $ مع $ a_2 $ ، $ \ cdots $ ، $ n-1 $ مع $ A_ {n-1} $ ، ترك فقط $ n $ غير متفائل. نرى أن الجانب الأيسر هو $$ (0 \ oplus a_0) \ oplus (1 \ oplus a_1) \ oplus (2 \ oplus a_2) \ oplus \ cdots (n-1 \ oplus a_ {n-1} ) \ oplus n. $ الآن، فقط حرك $ n $ إلى الجزء الأمامي من التعبير.

---

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

لا يوجد شيء خاص حول تهيئة المتغير المفقود مع $ n $ ، طول الصفيف. يمكنك بالتأكيد تهيئة ذلك مع أي رقم، بما في ذلك الصفر. ثم يجب عليك إقران أرقام المتبقية مع $ a_0، a_2، \ cdots، a_ {n-1} $ ( تعسفي < / em>، كل عدد بالضبط مرة واحدة). على سبيل المثال، لدينا

$$ 0 \ oplus (1 \ oplus a_0) \ oplus (2 \ oplus a_1) \ oplus \ cdots (n \ oplus a_ {n-1})=text { الرقم المفقود} $

في الواقع، ليس لدينا للقيام بالاقتران على الإطلاق. يمكننا حتى المسبق مباشرة $$ f (n)= 0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n =ابدأ {الحالات} n & \ text {if} n= 0 \ pmod4 \\ 1 & \ text {if} n= 1 \ pmod4 \\ n + 1 & \ text {if} n= 2 \ PMOD4 \\ 0 & \ text {if} n= 3 \ pmod4 \\ \ نهاية {الحالات} $ ثم حساب $$ f (n) \ oplus a_0 \ oplus a_1 \ oplus a_2 \ cdots \ oplus a_ {n-1}، $ والتي سوف تسفر عن العدد المفقود أيضا. وبالتالي لدينا البرنامج الأسرع التالي لحساب الرقم المفقود.

giveacodicetagpre.

الطريقة المذكورة أعلاه تشبه إلى حد كبير نهج # 4 صيغة Gauss على leetcode .

Answer 2

ابدأ بأقائمة أي أعداد صحيحة ن.تكرار الأعداد الصحيحة وحساب XOR إذا كانت هذه الأعداد الصحيحة 2N.ما هي النتيجة؟إعادة ترتيب الأعداد الصحيحة 2N بأي شكل من الأشكال وحساب XOR الخاصة بهم.ما هي النتيجة.قم بإزالة رقم X من القائمة وحساب XOR.ما هي النتيجة؟قم بإزالة رقم آخر Y وحساب XOR.ما هي النتيجة؟

الآن عد إلى مشكلتك، والإجابات التي قدمتها قبل إخبارك فورا ما سيكون عليه النتيجة.