Алгоритм поиска элементов, встречающихся только однажды в двух массивах - C#

Узнай цену своей работы

Формулировка задачи:

Всем привет, у меня такая проблема, помогите, нужно чтобы из двух массивов выводило. Элементы, которые встречаются только один раз и только в одном массиве.Ниже фотография моих массивов и код : 
class Program
    {
        static public int LinearSearchFirst<T>(T[] array, T value)
        {
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i].Equals(value)) return i;
            }
            return -1;
        }
 
        static public List<int> LinearSearchAll<T>(T[] array, T value)
        {
            List<int> res = new List<int>();
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i].Equals(value)) res.Add(i);
            }
            return res.Count > 0 ? res : null;
        }
 
        static public int BinarySearchFirst<T>(T[] array, T value, int left, int right)
        {
            if (left > right) return -1;
 
            int mid = (left + right) >> 1;
 
            if (((IComparable)array[mid]).CompareTo(value) < 0)
                return BinarySearchFirst(array, value, mid + 1, right);
            if (((IComparable)array[mid]).CompareTo(value) > 0)
                return BinarySearchFirst(array, value, left, mid - 1);
 
            return mid;
        }
 
        static public void BinarySearchAll<T>(T[] array, T value, int left, int right, List<int> res)
        {
            if (left > right)
            {
                res = null;
                return;
            }
 
            int mid = (left + right) >> 1;
 
            if (((IComparable)array[mid]).CompareTo(value) < 0)
            {
                BinarySearchAll(array, value, mid + 1, right, res);
                return;
            }
            if (((IComparable)array[mid]).CompareTo(value) > 0)
            {
                BinarySearchAll(array, value, left, mid - 1, res);
                return;
            }
            res.Add(mid);
            for (int i = mid + 1; i < right; i++)
            {
                if (array[i].Equals(value)) res.Add(i);
                else break;
            }
            for (int i = mid - 1; i > 0; i--)
            {
                if (array[i].Equals(value)) res.Add(i);
                else break;
            }
        }
 
        static public int Fib(int N)
        {
            int F1, F2;
            if (N == 0 || N == 1) return N;
            else if (N >= 2)
            {
                F1 = Fib(N - 1);
                F2 = Fib(N - 2);
                return F1 + F2;
            }
            return -1;
        }
 
        static public int FibonacciSearchFirst(int[] array, int value)
        {
            int j = 1, t = 0;
            while (Fib(j) < array.Length + 1) j++;
            int mid = array.Length - Fib(j - 2) + 1,
                f1 = Fib(j - 2),
                f2 = Fib(j - 3);
            bool finish = false;
            for (; ; )
            {
                if (finish || mid >= array.Length) break;
                if (mid > 0)
                    if (value == array[mid]) break;
                if (mid <= 0 || value > array[mid])
                {
                    if (f1 == 1) finish = true;
                    else
                    {
                        mid += f2;
                        f1 -= f2;
                        f2 -= f1;
                    }
                }
                else
                {
                    if (f2 == 0) finish = true;
                    else
                    {
                        mid -= f2;
                        t = f1 - f2;
                        f1 = f2;
                        f2 = t;
                    }
                }
            }
            if (finish) return array[0] == value ? 0 : -1;
            return mid;
        }
 
        static public List<int> FibonacciSearchAll(int[] array, int value)
        {
            List<int> res = new List<int>();
            res.Add(FibonacciSearchFirst(array, value));
            if (res[0] == -1) return null;
            for (int i = res[0] + 1; i < array.Length; i++)
            {
                if (array[i] == value) res.Add(i);
                else break;
            }
            for (int i = res[0] - 1; i > 0; i--)
            {
                if (array[i] == value) res.Add(i);
                else break;
            }
            return res;
        }
 
        static public int InterpolationSearchFirst(int[] array, int value)
        {
            int mid;
            int low = 0;
            int high = array.Length - 1;
 
            while (array[low] < value && array[high] > value)
            {
                mid = low + ((value - array[low]) * (high - low)) / (array[high] - array[low]);
 
                if (array[mid] < value)
                    low = mid + 1;
                else if (array[mid] > value)
                    high = mid - 1;
                else
                    return mid;
            }
 
            if (array[low] == value)
                return low;
            else if (array[high] == value)
                return high;
            else
                return -1;
        }
 
        static public List<int> InterpolationSearchAll(int[] array, int value)
        {
            List<int> res = new List<int>();
            res.Add(InterpolationSearchFirst(array, value));
            if (res[0] == -1) return null;
            for (int i = res[0] + 1; i < array.Length; i++)
            {
                if (array[i] == value) res.Add(i);
                else break;
            }
            for (int i = res[0] - 1; i > 0; i--)
            {
                if (array[i] == value) res.Add(i);
                else break;
            }
            return res;
        }
 
        static public int BlockSearchFirst<T>(T[] array, T value)
        {
            int blockSize = (int)Math.Sqrt(array.Length);
            int blocksCount = array.Length / blockSize;
            int lastBlockSize = array.Length % blockSize;
 
            for (int i = array.Length - lastBlockSize; i < array.Length; i++)
                if (array[i].Equals(value)) return i;
            for (int i = 0; i < blocksCount; i++)
                for (int j = 0; j < blockSize; j++)
                    if (array[i * blockSize + j].Equals(value)) return i * blockSize + j;
 
            return -1;
        }
 
        static public List<int> BlockSearchAll<T>(T[] array, T value)
        {
            int blockSize = (int)Math.Sqrt(array.Length);
            int blocksCount = array.Length / blockSize;
            int lastBlockSize = array.Length % blockSize, index = 0;
            List<int> res = new List<int>();
 
            for (int i = array.Length - lastBlockSize; i < array.Length; i++)
                if (array[i].Equals(value)) res.Add(i);
            for (int i = 0; i < blocksCount; i++)
                for (int j = 0; j < blockSize; j++)
                {
                    index = i * blockSize + j;
                    if (array[index].Equals(value)) res.Add(index);
                }
 
            return res.Count > 0 ? res : null;
        }
 
        static void Main(string[] args)
        {
            int length = 500, range = 250;
            bool print = true;
            List<int> A_list = new List<int>(length);
            List<int> B_list = new List<int>(length);
            int[] A_arr = new int[length];
            int[] B_arr = new int[length];
 
            Random rand = new Random();
            Stopwatch sw = new Stopwatch();
 
            for (int i = 0; i < A_arr.Length; i++)
            {
                A_list.Add(A_arr[i] = rand.Next(range));
                B_list.Add(B_arr[i] = rand.Next(range));
            }
            A_list.Sort();
            B_list.Sort();
            int[] A_arrSorted = A_list.ToArray();
            int[] B_arrSorted = B_list.ToArray();
            if (print)
            {
                Console.WriteLine("A array:");
                for (int i = 0; i < A_arr.Length; i++) Console.Write(A_arr[i] + ";\t");
                Console.WriteLine("\n\nB array:");
                for (int i = 0; i < B_arr.Length; i++) Console.Write(B_arr[i] + ";\t");
            }
          
         /*   double linAvg = 0, binAvg = 0, fibAvg = 0, interAvg = 0, blockAvg = 0, searchesCount = 0;
            List<int> indexes = new List<int>();
            List<int> tempIndexes1 = null;
            List<int> tempIndexes2 = null;
            List<int> tempIndexes3 = null;
            List<int> tempIndexes4 = null;
            List<int> tempIndexes5 = null;
            Console.WriteLine("\nSearching...");
            for (int i = 0; i < A_arr.Length; i++)
            {
                if (A_arr[i] % 2 == 0)
                {
                    searchesCount++;
 
                    //Линейный поиск
                    tempIndexes1 = new List<int>();
                    sw.Start();
                    tempIndexes1 = LinearSearchAll<int>(B_arr, A_arr[i]);
                    sw.Stop();
                    linAvg += sw.ElapsedTicks;
                    sw.Reset();
 
                    //Бинарный поиск
                    tempIndexes2 = new List<int>();
                    sw.Start();
                    BinarySearchAll<int>(B_arrSorted, A_arr[i], 0, B_arrSorted.Length - 1, tempIndexes2);
                    sw.Stop();
                    binAvg += sw.ElapsedTicks;
                    sw.Reset();
 
                    //Поиск Фибоначчи
                    tempIndexes3 = new List<int>();
                    sw.Start();
                    tempIndexes3 = FibonacciSearchAll(B_arrSorted, A_arr[i]);
                    sw.Stop();
                    fibAvg += sw.ElapsedTicks;
                    sw.Reset();
 
                    //Интерполяционный поиск
                    tempIndexes4 = new List<int>();
                    sw.Start();
                    tempIndexes4 = InterpolationSearchAll(B_arrSorted, A_arr[i]);
                    sw.Stop();
                    interAvg += sw.ElapsedTicks;
                    sw.Reset();
 
                    //М-блочный поиск
                    tempIndexes5 = new List<int>();
                    sw.Start();
                    tempIndexes5 = BlockSearchAll<int>(B_arr, A_arr[i]);
                    sw.Stop();
                    blockAvg += sw.ElapsedTicks;
                    sw.Reset();
 
                    if (tempIndexes1 != null && tempIndexes1.Count == 1 && !indexes.Contains(tempIndexes1[0])) indexes.Add(tempIndexes1[0]);
                }
            }
 
            indexes.Sort();
 
            linAvg /= searchesCount;
            binAvg /= searchesCount;
            fibAvg /= searchesCount;
            interAvg /= searchesCount;
            blockAvg /= searchesCount;
 
            Console.WriteLine("\nEven elements (" + indexes.Count + ") of the array A, which is in the array B in only one copy:\n");
            for (int i = 0; i < indexes.Count; i++) Console.Write("B[" + indexes[i] + "] = " + B_arr[indexes[i]] + ";\t");
            Console.WriteLine("\n\nLinear search average ticks:\t\t{0:0.##}", linAvg);
            Console.WriteLine("\nBinary search average ticks:\t\t{0:0.##}", binAvg);
            Console.WriteLine("\nFibonacci search average ticks:\t\t{0:0.##}", fibAvg);
            Console.WriteLine("\nInterpolation search average ticks:\t{0:0.##}", interAvg);
            Console.WriteLine("\nM-block search average ticks:\t\t{0:0.##}", blockAvg);
*/
 
            Console.WriteLine("\nEnd of program! Press any key to exit...");
            Console.WriteLine("\nEnd of program! Press any key to exit...");
            Console.ReadKey();
             
            Console.ReadKey();
        }
    }
}

Решение задачи: «Алгоритм поиска элементов, встречающихся только однажды в двух массивах»

textual
Листинг программы 
class Program {
        static void Main(string[] args) {
            int[] first = { 1, 1, 2, 3, 3, 3, 4, 4, 5, 6, 6 };
            int[] second = { 2, 3, 4, 6, 6, 6, 7, 8, 8, 8, 9 };
 
            var uniqueNumbers = first.Concat(second)
                                     .GroupBy(n => n)
                                     .Where(g => g.Count() == 1);
 
            if (uniqueNumbers.Count() == 0) {
                Console.WriteLine("Нет элементов, которые встречаются только один раз и только в одном из массивов.");
            }
            else {
                Console.WriteLine("Элементы, которые встречаются только один раз и только в одном из массивов:");
                foreach (var number in uniqueNumbers) {
                    Console.Write(number.Key + " ");
                }
            }
 
            Console.ReadKey();
        }
    }

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 4.4 из 5
Похожие ответы