Các cách tìm số thiếu trong mảng đã sắp xếp không dùng hàm có sẵn C#

Có ba phương pháp như sau:

• Phương pháp 1: Dùng công thức n(n+1)/2 đếm tổng số phần tử, trừ đi tổng các phần tử trong mảng.
• Phương pháp 2: Tạo mảng mới, duyệt mảng gốc, đánh dấu true cho số được tìm thấy.
• Phương pháp 3: Dùng phép XOR, cho ra số thiếu.

Ví dụ

using System;

namespace ConsoleApplication
{
    public class Arrays
    {
        public int MissingNumber1(int[] arr)
        {
            int totalcount = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                totalcount += arr[i];
            }
            int count = (arr.Length * (arr.Length + 1)) / 2;
            return count - totalcount;
        }

        public int MissingNumber2(int[] arr)
        {
            bool[] tempArray = new bool[arr.Length + 1];
            int element = -1;
            for (int i = 0; i < arr.Length; i++)
            {
                int index = arr[i];
                tempArray[index] = true;
            }
            for (int i = 0; i < tempArray.Length; i++)
            {
                if (tempArray[i] == false)
                {
                    element = i;
                    break;
                }
            }
            return element;
        }

        public int MissingNumber3(int[] arr)
        {
            int result = 1;
            for (int i = 0; i < arr.Length; i++)
            {
                result = result ^ arr[i];
            }
            return result;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Arrays a = new Arrays();
            int[] arr = { 0, 1, 3, 4, 5 };
            Console.WriteLine(a.MissingNumber1(arr));
            Console.WriteLine(a.MissingNumber2(arr));
            Console.WriteLine(a.MissingNumber3(arr));
            Console.ReadLine();
        }
    }
}

Kết quả

2
2
2

Giải thích: Ba phương pháp tìm số thiếu trong mảng {0,1,3,4,5} (thiếu 2). Phương pháp 1: tổng lý thuyết - tổng thực tế. Phương pháp 2: mảng boolean đánh dấu. Phương pháp 3: XOR tất cả chỉ số và giá trị, số thiếu còn lại. Cả 3 đều cho kết quả 2.