Объединение двух списков в один и сортировка элементов

Question

Есть ли способ объединить (объединить без дубликатов) два заданных списка в один и сохранить элементы отсортированным способом, используя ONE for loop?

Кроме того, я ищу решение, которое не использует методы API (например, объединение, сортировка и т. Д.).

Пример кода.

private static void MergeAndOrder() 
{
var listOne = new List<int> {3, 4, 1, 2, 7, 6, 9, 11}; 
var listTwo = new List<int> {1, 7, 8, 3, 5, 10, 15, 12}; 

//Without Using C# helper methods...
//ToDo.............................

//Using C# APi.
var expectedResult = listOne.Union(listTwo).ToList(); 
expectedResult.Sort();//Output: 1,2,3,4,5,6,7,8,9,10,11,12,15
//I need the same result without using API methods, and that too by iterating over items only once.


}

PS: мне задавали этот вопрос в интервью, но пока не смог найти ответ.

Answer 1

Без предварительного условия, что оба списка отсортированы перед операцией слияния + сортировки, вы не можете сделать это за O (n) время (или «используя один цикл»).

Добавьте это предварительное условие, и проблема очень проста.

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

В псевдокоде:

List a = { 1, 3, 5, 7, 9 }
List b = { 2, 4, 6, 8, 10 }
List result = { }
int i=0, j=0, lastIndex=0
while(i < a.length || j < b.length)
    // If we're done with a, just gobble up b (but don't add duplicates)
    if(i >= a.length)
        if(result[lastIndex] != b[j])
            result[++lastIndex] = b[j]
        j++
        continue

    // If we're done with b, just gobble up a (but don't add duplicates)
    if(j >= b.length)
        if(result[lastIndex] != a[i])
            result[++lastIndex] = a[i]
        i++
        continue

    int smallestVal

    // Choose the smaller of a or b
    if(a[i] < b[j])
        smallestVal = a[i++]
    else
        smallestVal = b[j++]

    // Don't insert duplicates
    if(result[lastIndex] != smallestVal)
        result[++lastIndex] = smallestVal
end while

Answer 2

Почему вы не можете использовать методы API? Изобретать колесо глупо. Кроме того, это звонок .ToList(), который убивает вас. Никогда не звоните .ToList() или .ToArray() до тех пор, пока вам это не понадобится, потому что они нарушают вашу ленивую оценку.

Сделайте так, и вы перечислите в списках минимально необходимую сумму:

var expectedResult = listOne.Union(listTwo).OrderBy(i => i);

Это выполнит объединение в одном цикле с использованием хэш-набора, а отложенное выполнение означает, что базовый проход для сортировки будет добавлен в объединение. Но я не думаю, что возможно закончить сортировку за одну итерацию, потому что сортировка не является операцией O (n).

Answer 3

Используя итераторы и потоковый интерфейс, задача не так сложна:

класс MergeTwoSortedLists { static void Main (строка [] args) {

        var list1 = new List<int?>() {
            1,3,5,9,11
        };

        var list2 = new List<int?>() {
            2,5,6,11,15,17,19,29
        };

        foreach (var c in SortedAndMerged(list1.GetEnumerator(), list2.GetEnumerator())) {
            Console.Write(c+" ");
        }

        Console.ReadKey();
    }

    private static IEnumerable<int> SortedAndMerged(IEnumerator<int?> e1, IEnumerator<int?> e2) {
        e2.MoveNext();
        e1.MoveNext();

        do {
            while (e1.Current < e2.Current) {
                if (e1.Current != null) yield return e1.Current.Value;
                e1.MoveNext();
            }

            if (e2.Current != null) yield return e2.Current.Value;
            e2.MoveNext();
        } while (!(e1.Current == null && e2.Current == null));
    }
}

Answer 4

    private static void MergeTwoSortedArray(int[] first, int[] second)
    {
        //throw new NotImplementedException();

        int[] result = new int[first.Length + second.Length];

        int i=0 , j=0 , k=0;

        while(i < first.Length && j <second.Length)
        {
            if(first[i] < second[j])
            {
                result[k++] = first[i++];
            }
            else
            {
                result[k++] = second[j++];
            }
        }

        if (i < first.Length)
        {
            for (int a = i; a < first.Length; a++)
                result[k] = first[a];
        }

        if (j < second.Length)
        {
            for (int a = j; a < second.Length; a++)
                result[k++] = second[a];
        }

        foreach (int a in result)
            Console.Write(a + " ");

        Console.WriteLine();
    }

Answer 5

Попробуйте это:

      public static IEnumerable<T> MergeWith<T>(IEnumerable<T> collection1, IEnumerable<T> collection2,
            IComparer<T> comparer)
        {
            using (var enumerator1 = collection1.GetEnumerator())
            using (var enumerator2 = collection2.GetEnumerator())
            {
                var isMoveNext1 = enumerator1.MoveNext();
                var isMoveNext2 = enumerator2.MoveNext();

                do
                {
                    while (comparer.Compare(enumerator1.Current, enumerator2.Current) < 0 || !isMoveNext2)
                    {
                        if (isMoveNext1)
                            yield return enumerator1.Current;
                        else
                            break;

                        isMoveNext1 = enumerator1.MoveNext();
                    }

                    if (isMoveNext2)
                        yield return enumerator2.Current;

                    isMoveNext2 = enumerator2.MoveNext();
                } while (isMoveNext1 || isMoveNext2);
            }
        }

Answer 6

Это будет работать только для списков целых чисел, но к счастью, это то, что у вас есть!

List<int> sortedList = new List<int>();
foreach (int x in listOne)
{
    sortedList<x> = x;
}
foreach (int x in listTwo)
{
    sortedList<x> = x;
}

Это использует значения в каждом списке в качестве позиции индекса, в которой следует сохранить значение. Любые повторяющиеся значения перезапишут предыдущую запись в этой позиции индекса. Он соответствует требованию только одной итерации по значениям.

Это, конечно, означает, что в списке будут «пустые» позиции.

Я подозреваю, что вакансия уже заполнена ...: -)

Answer 7

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

int[] values = new int[ Integer.MAX ]; // initialize with 0
int size1 = list1.size();
int size2 = list2.size();

for( int pos = 0; pos < size1 + size2 ; pos++ )
{
     int val =  pos > size1 ? list2[ pos-size1 ] : list1[ pos ] ;
     values[ val ]++;
}

Тогда вы можете утверждать, что у вас есть отсортированный массив в «особой» форме :-) Чтобы получить чистый отсортированный массив, вам нужно пройти по массиву values, пропустить все позиции с количеством 0 и собрать окончательный список.

Answer 8

var listOne = new List<int> { 3, 4, 1, 2, 7, 6, 9, 11 };
var listTwo = new List<int> { 1, 7, 8, 3, 5, 10, 15, 12 };
var result = listOne.ToList();

foreach (var n in listTwo)
{
  if (result.IndexOf(n) == -1)
    result.Add(n);
}

Answer 9

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