0

Насчет дубликатов: {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;
    }
5
  • Что значит "можно"? Или они неубывающие, тогда применяете модифицированную процедуру Merge из сортировки слиянием,, либо произвольные, тогда мучаетесь
    – MBo
    28 июн 2022 в 1:48
  • Спасибо за ваш ответ я понял главную свою глупость) Я относительно новичок. Думал находить пересечение неотсортированных массивов, что сложнее. А до merge я пока не дошёл. Пока пилю алгоритмы
    – Sheeba334
    28 июн 2022 в 2:11
  • Пересечение неотсортированных проще делать через словари/map. А для начала стоит точно сформулировать, как поставлена задача. Какой должен быть результат? как обходиться с дубликатами?
    – MBo
    28 июн 2022 в 2:35
  • 1
    {1,2,2,4} пересечение {1,2,2,3} = {1,2,2}. А пересечение {1,2,2,4} и {1,2,3}?
    – MBo
    28 июн 2022 в 6:30
  • OK, код в ответе выполняет пересечение {1,2,2,4} и {1,2,3} = {1,2}
    – MBo
    29 июн 2022 в 1:52

1 ответ 1

1

Давайте попробуем пересечение за линейное время. Пишу прямо здесь, не тестировал.

 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;
    }
7
  • Всё протестировал, всё круто(только Math.Min вместо min, если брать строго). Насчёт урезать длину, это лучший способ: arrayOfIntersection = arrayOfIntersection[..k]; ? Я так понимаю такой способ подходит для вычисления разницы множеств. Пойду пробовать. И хотел бы спросить: считается ли дублированием кода то, что находится в теле метода по вычислению длинны и в методе по нахождению массива пересечения? Они отличаются одной строчкой
    – Sheeba334
    29 июн 2022 в 1:53
  • @Sheeba334 Да, заодно можно разницу вычислять, только в конце придётся ещё добавить обработку концов массивов. Про лучший способ уменьшить длину я не знаю, не шарпист. Если урезать длину - то предварительного вычисления её не требуется.
    – MBo
    29 июн 2022 в 2:00
  • я понимаю, но чисто фактически это дублирование? И спасибо за ответы и редактирование. Очень информативно
    – Sheeba334
    29 июн 2022 в 2:04
  • чисто фактически это дублирование? зависит от того, кто как интерпретирует ;) На мой взгляд- да, но вычленение одинакового кода вроде создания итератора по одинаковым элементам непомерно усложняет.
    – MBo
    29 июн 2022 в 2:09
  • Кстати, по смыслу (семантически более правильно) для создании результата неизвестного размера больше подходит список, а не массив
    – MBo
    29 июн 2022 в 2:21

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.