Поиск в массивые - C#
Формулировка задачи:
Доброе время суток. Подкинули задачку которую мне интересно решить но не как не могу.
Задача:
"У вас есть два массива целых чисел A и В. Массивы не сортированные. Напишите, на любом языке, функцию, которая максимально быстро найдет пересечение этих массивов (список элементов, которые есть в обоих массивах)."
Товарищ дал подсказку что это на расчет сложности алгоритма, но поскольку это было еще до армии можно сказать что для меня это не о чем не говорит.
Я склепал программу где попытался решить задачку.
Вот она:
Люди добрые пожало сто посмотрите где мой косяк в третьем решении и если есть то предложите свой вариант решения.
class Program { static void Main(string[] args) { MyArr Arr = new MyArr(); Console.ReadKey(); } } class MyArr { private int[] Mas1; private int[] Mas2; private Random RR = new Random(); private int magik = 4; public MyArr() { Zap(); /*foreach (int i in Mas1) { Console.Write(i); } Console.WriteLine(); foreach (int i in Mas2) { Console.Write(i); }*/ Console.WriteLine(); One();// банальный перебор просто так для сравнения Console.WriteLine(); Two();// сугубо моя попытка ответить на вопрос Console.WriteLine(); //Three(); // не работает Console.WriteLine(); Four();// случайно нашел такой вариант решения но как он работает не разобрал =( } private void Zap() { Mas1 = new int[ magik ]; Mas2 = new int[ magik ]; for( int i = 0 ; i < magik ; i++ ) { Mas1[ i ] = RR.Next( magik ); Mas2[ i ] = RR.Next( magik ); } } private void One() { for(int i = 0 ; i < Mas2.Length ; i++ ) { for( int j = 0 ; j < Mas1.Length ; j++ ) { if( Mas2[ i ] == Mas1[ j ] ) { Console.Write( " " + Mas2[ i ] ); } } } } private void Two() { int i = 0 ; do { for ( int j = 0 ; j < Mas1.Length ; j++ ) { if ( Mas2[ i ] == Mas1[ j ] ) { Console.Write( " " + Mas2[ i ] ); i++; if ( !( i == Mas2.Length ) ) { j = -1; } else { j = Mas1.Length - 1; } } } i++; } while ( i < Mas2.Length ); } private void Three() { // знакомый нашел решение на JavaScript но у меня ошибка с переполнением вылазит или 0 /* function intersection(A, B) { var m = A.length, n = B.length, c = 0, C = []; for (var i = 0; i < m; i++) { var j = 0, k = 0; while (B[j] !== A[ i ] && j < n) j++; while (C[k] !== A[ i ] && k < c) k++; if (j != n && k == c) C[c++] = A[ i ]; } return C; } */ int m = Mas1.Length , n = Mas2.Length , c = 0; int[] Mas3 = { 0 }; for ( int i = 0 ; i < m ; i++ ) { int j = 0, g = 0; while( ( Mas2 [ j ] != Mas1[ i ] ) && ( j < n ) ) { j++; while ( ( Mas3[ g ] != Mas1[ i ] ) && ( g < c ) ) { g++; if ( j != n && g == c ) { Array.Resize<int>( ref Mas3 , c++ ); Mas3[ c ] = Mas1[ i ]; } } } } for( int i = 0 ; i < Mas3.Length ; i++ ) { Console.Write( " " + Mas3[ i ] ); } } private void Four() { IEnumerable<int> bot = Mas1.Intersect( Mas2 ); foreach ( int i in bot ) { Console.Write( " " + i ); } } }
Решение задачи: «Поиск в массивые»
textual
Листинг программы
static void Main(string[] args) { int[] a = new[] { 1, 2, 3, 4, 5, 6, 7 }; int[] b = new[] { 2, 4, 6, 8 }; var result = GetList(a, b); foreach (var i in result) Console.Write("{0} ", i); Console.ReadLine(); } static IEnumerable<int> GetList(IEnumerable<int> a, IEnumerable<int> b) { foreach (int x in a) if (b.Contains(x)) yield return x; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д