Найти пару чисел в 2-мерном массиве в C #

Question

какой быстрый способ найти пару чисел в двумерном массиве

У меня есть этот массив

 int[,] numbers = new int[,] { { 5, 2 }, { 5, 1 }, { 5, 0 } , ........... };

у меня есть целые числа, такие как x,y

я хочу вернуть индекс этой пары apper в массиве

если пары не существует, retun false

спасибо

Answer 1

«Самый быстрый» расплывчато; быстрее всего написать или быстрее всего выполнить?

Самое быстрое, что вы можете получить в неупорядоченном списке, будет линейным, а фактические наилучшие и худшие случаи будут зависеть от входных данных. Быстрее всего в неупорядоченном списке, вероятно, будет:

var i = 0;
foreach(var subarray in numbers)
{
   if(subarray[0] == x && subarray[1] == y || subarray[0] == y && subarray[1] == x)
     return i;
   i++;
}

Наилучшим случаем является то, что первый элемент имеет элементы в порядке; 1 элемент, 2 сравнения равенства. В худшем случае это не там; n элементов, n * 4 сравнения равенства.

Вы можете "быстро потерпеть неудачу" в ситуациях, когда маловероятно, что совпадение будет найдено, проверив, есть ли в подмассиве хотя бы один элемент с хотя бы одной из координат. Если нет, не стоит проверять точное совпадение. Это наихудший случай, когда элемент является последним, не по порядку (n * 2 элемента, n * 6 сравнений), но в лучшем случае его там нет (n элементов, n * 2 сравнений, которые, если этот случай скорее всего лучше предыдущего).

Наконец, алгоритм «fast fast» позволяет с помощью Linq сузить число элементов, для которых вы выполняете полный набор условных проверок; Сначала вы ищите элементы, которые имеют хотя бы одну из координат (требуется максимум две проверки), а затем проверяете только те элементы, которые точно совпадают (максимум четыре проверки). Затем вы сканируете массив для первого найденного элемента, который является относительно быстрой ссылочной проверкой.

var result = numbers.Where(a=>a[0] == x || a[0] == y)
   .Where(a=>a[0] == x && a[1] == y || a[0] == y && a[1] == x)
   .FirstOrDefault();

if(result != null) return Array.IndexOf(numbers, result);

В лучшем случае его там нет (n элементов, n * 2 сравнений). Лишь немного хуже вероятный случай, когда только один элемент имеет любую из координат (n + 1 элементов, n * 2 + (2 или 4) сравнения). В худшем случае совпадение - это последний элемент, вышедший из строя, И каждый элемент в списке имеет первую координату, которая является x или y (n * 3 элемента, n * 7 сравнений, но это ЧРЕЗВЫЧАЙНО маловероятно в большинстве реальных данных) , Средний регистр будет зависеть от количества элементов, которые имеют хотя бы одну из координат в качестве первого значения.

Answer 2

Если массив не упорядочен, лучшее, что вы можете сделать - это линейный поиск - либо строка за строкой, столбец за столбцом, либо даже по диагонали.

Если упорядочены какие-либо размеры массива, тогда вы могли бы использовать двоичный поиск.

Если данные упорядочены и также соответствуют некоторому типу распределения, вы можете использовать поиск корреляции распределения, который может быть немного более эффективным, чем двоичный поиск.

Answer 3

Выполните сортировку двумерного массива, а затем используйте бинарный поиск.

Answer 4

Если массив упорядочен, вы можете использовать бинарный поиск. В противном случае вам придется выполнить линейный поиск.