K-й элемент из двух отсортированных массивов

Question

Даны два отсортированных массива A и B размера M и N соответственно и элемент k.Задача состоит в том, чтобы найти элемент, который будет в k-й позиции окончательного отсортированного массива.

Вопрос от GeeksforGeeks

Это код, который я написал для вышеуказанного вопроса.Я только что объединил данные два массива в третий массив, а затем отсортировал его.Я написал на языке Си.Мне не хватает знаний о том, как написать код оптимизированным способом.Пожалуйста, помогите мне, дайте мне знать, как оптимизировать код так, чтобы он занимал меньше времени выполнения.

 for (i = 0; i <= n1 - 1; i++)
{
  scanf ("%d", &a[i]);
}
  for (i = 0; i <= n2 - 1; i++)
{
  scanf ("%d", &b[i]);
}
  for (i = 0; i < n1; i++)
{
  c[i] = a[i];
}
  for (j = n1, i = 0; j <= z - 1 && i <= n2 - 1; j++, i++)
{
  c[j] = b[i];
}
  for (i = 0; i <= z - 1; i++)
{
  for (j = i + 1; j <= z - 1; j++)
    {
      if (c[i] > c[j])
    {
      temp = c[j];
      c[j] = c[i];
      c[i] = temp;
    }
    }
}
  printf ("%d", c[q]);

У меня есть вывод, но проблема, с которой я сталкиваюсь, состоит в том, что .. Ваша программа взяла большепревышено ожидаемое время. Превышен лимит времени Ожидаемый лимит времени <0,324сек

Answer 1

Несколько псевдокодов MergeSort, алгоритма эффективного объединения двух отсортированных массивов, который является наихудшим в оптимальном случае:

function void mergesort(S array; l,r integer) {
    if (l<r) then
    #Sort each
        ~50% of array
        m := (r-l)
        div 2;
        mergesort(S, l, l+m);
        mergesort(S, l+m+1, r);
        #merges two sorted lists
        merge( S, l, l+m ,r);
    else
        # Nothing to do, 1-element list
    end if;
}


function void merge(S array; l,m,r integer) {
    B: array[1..r-l+1];
    i := l;
    # Start of 1st list
    j := m+1;
    # Start of 2nd list
    k := 1;
    # Target list
    while (i<=m) and (j<=r) do
        if S[i]<=S[j] then
            B[k] := S[i]; # From 1st list
            i := i+1;
        else
            B[k] := S[j]; # From 2nd list
            j := j+1;
        end if;
        k := k+1;
    # Next target
    end while;
    if i>m then
    # What remained?
        copy S[j..r] to B[k..k+r-j];
    else
        copy S[i..m] to B[k..k+m-i];
    end if;
    # Back to original list
    copy B[1..r-l+1] to S[l..r];
}