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

Tìm số bị thiếu

Tạo mảng mới, duyệt toàn bộ mảng gốc, đánh dấu true tại chỉ số tương ứng nếu tìm thấy số. Duyệt mảng mới, trả về phần tử false đầu tiên là số bị thiếu.

Tìm phần tử lặp

Phần tử true đầu tiên trong mảng mới sẽ là phần tử lặp.

Ví dụ

using System;

namespace ConsoleApplication
{
    public class Arrays
    {
        public void MissingNumberAndRepeatedNumber(int[] arr)
        {
            bool[] tempArray = new bool[arr.Length + 1];
            int missingelement = -1;
            int repeatingelement = -1;
            for (int i = 0; i < arr.Length; i++)
            {
                int index = arr[i];
                if (!tempArray[index])
                {
                    tempArray[index] = true;
                }
            }
            for (int i = 0; i < tempArray.Length; i++)
            {
                if (!tempArray[i])
                {
                    missingelement = i;
                    break;
                }
            }
            int[] tempArray1 = new int[arr.Length + 1];
            for (int i = 0; i < arr.Length; i++)
            {
                int index = arr[i];
                if (tempArray1[index] == 0)
                {
                    tempArray1[index] = 1;
                }
                else if (tempArray1[index] == 1)
                {
                    tempArray1[index] = 2;
                }
            }
            for (int i = 0; i < tempArray1.Length; i++)
            {
                if (tempArray1[i] == 2)
                {
                    repeatingelement = i;
                    break;
                }
            }
            Console.WriteLine(missingelement);
            Console.WriteLine(repeatingelement);
        }
    }

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

Kết quả

2
1

Giải thích: Mảng {0,1,1,3,4} có độ dài 5, chứa số 0-4. Số 2 bị thiếu, số 1 lặp 2 lần. Sử dụng mảng boolean và mảng int đếm tần suất. Phức tạp O(n) thời gian, O(n) không gian.