استعادة المفقود
الوصف
في عالم الأمن السيبراني المظلم، تواجه شبكة سرية تُعرف باسم شبكة الظلال تهديدًا خطيرًا. يتم حماية الشبكة عبر رموز سرية مكونة من أرقام فريدة. أحد هذه الرموز فُقد، وتم تشفيره بين بيانات مشوشة.
مهمتك كخبير في الأمن السيبراني هي تحليل البيانات المعطاة وتحديد أصغر رقم سري مفقود. عليك أن تتحرك بسرعة، حيث يُمكن لهذا الكود أن يكون مفتاحًا لمنع اختراق واسع للشبكة. البيانات قد تكون مشوشة، تحتوي على أرقام سلبية وأخرى خارج النطاق، لكن عليك إيجاد الرقم المفقود بأقل استهلاك للوقت والموارد.
-
المدخلات:
-
قائمة من الأرقام المشوشة (قد تكون موجبة، سالبة، أو صفر).
-
المطلوب:
-
العثور على أصغر رقم موجب غير موجود في القائمة.
-
القيود:
-
الحل يجب أن يعمل بكفاءة:
-
O(n) من حيث الزمن.
-
O(1) من حيث المساحة الإضافية.
-
الهدف:
-
حماية الشبكة عبر تحديد الرقم السري المفقود بسرعة ودقة.
مثال توضيحي:
لنفترض أن لدينا هذه القائمة:
[3, 4, -1, 1]
-
تجاهل الأرقام السلبية والصفرية:
-1ليست مهمة. -
إعادة ترتيب الأرقام: نضع كل رقم في مكانه المناسب:
-
الرقم
1يجب أن يكون في المكان 0. -
الرقم
3يجب أن يكون في المكان 2.
بالتالي بعد إعادة ترتيب القائمة، ستكون:
[1, -1, 3, 4]
-
البحث عن أصغر رقم مفقود:
-
بعد الترتيب، الرقم المفقود هو
2، لأنه لم يوجد في أي مكان.
المخرجات:
2
المخطط الزمني:
-
O(n): لأننا نمر عبر المصفوفة مرة واحدة فقط، ونقوم بالتبديل بين العناصر.
-
O(1): لأننا لا نستخدم مساحة إضافية سوى المؤشرات التي تعد في الذاكرة فقط.
أمثلة
| المدخلات | المخرجات المتوقعة |
|---|---|
nums = [1,2,0] | 3 |
nums = [3,4,-1,1] | 2 |
nums = [7,8,9,11,12] | 1 |
nums = [1,2,3,4,5] | 6 |
الحل
from typing import List
def firstMissingPositive(nums: List[int]) -> int:
s = set(nums)
i = 1
while i in s:
i += 1
return i