Задание с пересечением 2 неубывающих массивов
Насчет дубликатов: {1,2,2,4} пересечение {1,2,2,3} = {1,2,2}.А пересечение {1,2,2,4} и {1,2,3} = {1,2}. Как сделать красивее, лучше, читабельнее?
public static int[] FindIntersection(int[] arrayFirst, int[] arraySecond)
{
int[] arrayOfIntersection = new int[CalculateLengthOfIntersectionArray(arrayFirst, arraySecond)];
int indexOfIntersectedArray = 0;
int indexOfSecondArrayToStart = 0;
for (int i = 0; i < arrayFirst.Length; i++)
{
for (int j = indexOfSecondArrayToStart; j < arraySecond.Length; j++)
{
if (arrayFirst[i] == arraySecond[j])
{
arrayOfIntersection[indexOfIntersectedArray] = arraySecond[j];
indexOfIntersectedArray++;
indexOfSecondArrayToStart = j + 1;
break;
}
}
}
return arrayOfIntersection;
}
public static int CalculateLengthOfIntersectionArray(int[] arrayFirst, int[] arraySecond)
{
int countOfIntersectedElements = 0;
int indexOfSecondArrayToStart = 0;
for (int i = 0; i < arrayFirst.Length; i++)
{
for (int j = indexOfSecondArrayToStart; j < arraySecond.Length; j++)
{
if (arrayFirst[i] == arraySecond[j])
{
indexOfSecondArrayToStart = j + 1;
countOfIntersectedElements++;
break;
}
}
}
return countOfIntersectedElements;
}
public static int[] SortArrayAscending(int[] array)
{
for (int i = 0; i < array.Length - 1; i ++)
for (int j = i + 1; j < array.Length; j++)
if (array[i] > array[j])
{
(array[i], array[j]) = (array[j], array[i]);
}
return array;
}
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Давайте попробуем пересечение за линейное время. Пишу прямо здесь, не тестировал.
public static int[] FindIntersection(int[] arrayFirst, int[] arraySecond)
{
int len1 = arrayFirst.Length;
int len2 = arraySecond.Length;
int[] arrayOfIntersection = new int[min(len1, len2)];
int i = 0, j = 0, k = 0;
while (i < len1 && j < len2) {
if (arrayFirst[i] < arraySecond[j])
i++;
else if (arrayFirst[i] > arraySecond[j])
j++;
else {
arrayOfIntersection[k++] = arrayFirst[i++];
j++;
}
}
//урезать длину arrayOfIntersection до k
return arrayOfIntersection;
}