Tìm số bị thiếu trong dãy số trong C#

Sử dụng LINQ để tìm các số bị thiếu trong một dãy số nguyên liên tiếp. Kết hợp Enumerable.Range để tạo dãy hoàn chỉnh và Except để tìm phần tử thiếu.

Thuật toán

1. Tìm min và max của danh sách
2. Tạo dãy hoàn chỉnh từ min đến max với Enumerable.Range
3. Dùng Except để lấy phần tử có trong dãy hoàn chỉnh nhưng không có trong danh sách gốc

Ví dụ: Danh sách {1, 2, 3, 5, 8, 9}

List myList = new List { 1, 2, 3, 5, 8, 9 };
// Thiếu: 4, 6, 7

Mã nguồn hoàn chỉnh

using System.Collections.Generic;
using System;
using System.Linq;

public class Program
{
    public static void Main()
    {
        List myList = new List { 1, 2, 3, 5, 8, 9 };
        
        Console.WriteLine("Số ban đầu:");
        foreach (int val in myList) Console.WriteLine(val);
        
        int a = myList.OrderBy(x => x).First();
        int b = myList.OrderBy(x => x).Last();
        
        // Tạo dãy hoàn chỉnh từ a đến b
        List fullRange = Enumerable.Range(a, b - a + 1).ToList();
        
        // Tìm phần tử thiếu
        List missing = fullRange.Except(myList).ToList();
        
        Console.WriteLine("\nSố bị thiếu:");
        foreach (int res in missing)
            Console.WriteLine(res);
    }
}

Kết quả

Số ban đầu:
1
2
3
5
8
9

Số bị thiếu:
4
6
7

Giải thích

• Enumerable.Range(start, count): Tạo dãy start, start+1, ..., start+count-1
• b - a + 1: Số lượng phần tử từ a đến b (inclusive)
• Except: Trả về phần tử có trong tập thứ nhất nhưng không có trong tập thứ hai

Mở rộng: Tìm khoảng trống (gaps)

// Trả về các khoảng (start, end) của dãy thiếu
var gaps = missing
    .Select((v, i) => new { Value = v, Index = i })
    .GroupBy(x => x.Value - x.Index)
    .Select(g => new { Start = g.First().Value, End = g.Last().Value });

// Kết quả cho {1,2,3,5,8,9}: {4,4}, {6,7}

Lưu ý

• Yêu cầu danh sách không trùng lặp (nếu có duplicate, dùng Distinct() trước).
• Hiệu suất O(n log n) do OrderBy. Nếu đã sắp xếp, bỏ qua bước sort.
• Với dãy rất lớn, cân nhắc dùng HashSet để O(n).