إيجاد أقل فرق بين عنصرين في مصفوفة C++ باستخدام الفرز

لإيجاد أقل فرق مطلق بين عنصرين في مصفوفة C++ نفرز نسخة من القيم ثم نقارن العناصر المتجاورة. لا يتعلق التمرين بمساحة شكل هندسي؛ الناتج فرق عددي غير سالب. يجب أن تحتوي البيانات على عنصرين على الأقل حتى يكون السؤال معرفًا.

#include <algorithm>
#include <iostream>
#include <limits>
#include <optional>
#include <vector>

std::optional<unsigned long long> minimumDifference(std::vector<long long> values) {
    if (values.size() < 2) return std::nullopt;
    std::sort(values.begin(), values.end());
    auto best = std::numeric_limits<unsigned long long>::max();
    for (std::size_t i = 1; i < values.size(); ++i) {
        // Unsigned subtraction safely represents the full signed-domain distance.
        auto distance = static_cast<unsigned long long>(values[i])
                      - static_cast<unsigned long long>(values[i - 1]);
        best = std::min(best, distance);
    }
    return best;
}

int main() {
    int count{};
    std::cout << "Count (2..100000): ";
    if (!(std::cin >> count) || count < 2 || count > 100000) {
        std::cout << "Invalid count.\n";
        return 1;
    }
    std::vector<long long> values(static_cast<std::size_t>(count));
    for (auto& value : values)
        if (!(std::cin >> value)) { std::cout << "Invalid number.\n"; return 1; }
    std::cout << "Minimum difference: " << *minimumDifference(values) << '\n';
}

بعد الفرز لا يمكن لعنصرين يفصل بينهما عنصر ثالث أن يعطيا فرقًا أصغر من كل الفروق المجاورة بينهما. لذلك نمر مرة واحدة بعد الفرز ونحفظ أصغر مسافة. التكلفة O(n log n) بسبب الفرز، بدل مقارنة جميع الأزواج O(n²). تستقبل الدالة نسخة من vector حتى لا تغير ترتيب المصدر.

القيمتان المتساويتان تعطيان فرقًا صفرًا حتى لو كانتا في موضعين مختلفين. القائمة -5 و-2 و7 أقل فرق فيها 3. استخدمنا طرحًا غير موقع بعد الترتيب لتمثيل الفرق الكامل بين أصغر وأكبر قيمة long long؛ حساب abs(a-b) بنوع موقع قد يتجاوز المجال قبل الوصول إلى abs.

أدخل العدد ثم العناصر؛ مثلًا 3 ثم 3 و10 و1 يعطي أقل فرق 2. تعيد الدالة nullopt للقائمة الفارغة أو المفردة، وتمنع واجهة المثال هذه الحالات مسبقًا. حد عدد العناصر 100000 اختيار لحجم التمرين. لا نستخدم أسماء مصفوفات قبل تعريفها أو نعيد النتيجة داخل أول مقارنة فقط.

احفظ المثال في ملف main.cpp واختر معيار C++17 في محررك. مع GCC أو Clang يمكنك الترجمة بالأمر g++ -std=c++17 -Wall -Wextra -pedantic main.cpp -o main ثم تشغيل الملف الناتج. ترجم كل مثال كبرنامج مستقل؛ لا تجمع دوال main من دروس مختلفة في ملف واحد.

الكود النصي أعلاه هو النسخة المصححة؛ قد تختلف المواد المرئية السابقة في أسماء المتغيرات أو طريقة التشغيل.