Кухня(); Второй сезон - 72/79



72. Даны две последовательности a1 ≤ a2 ≤… ≤ аn и b1 ≤ b2 ≤… ≤ bn. Образовать из них новую последовательность чисел так, чтобы она тоже была неубывающей.

16 комментариев

kolust
А в чем собственно проблема???
terranum
Правила тут
Airon
"(дополнительный массив не использовать)"?
public static int[] merge(int[] array0, int[] array1) {
    if(array0 == null && array1 == null)
        return null;
    if(array0 == null)
        return array1;
    if(array1 == null)
        return array0;
    if(array0.length == 0)
        return array1;
    if(array1.length == 0)
        return array0;
    int[] result = new int[array0.length + array1.length];
    return merge(array0, 0, array1, 0, result, 0);
}

private static int[] merge(int[] array0, int i0, int[] array1, int i1, int[] result, int iR) {
    if(iR == result.length)
        return result;
    if(i0 == array0.length) {
        System.arraycopy(array1, i1, result, iR, array1.length - i1);
        return result;
    }
    if(i1 == array1.length) {
        System.arraycopy(array0, i0, result, iR, array0.length - i0);
        return result;
    }
    if(array0[i0] < array1[i1]) {
        result[iR] = array0[i0];
        return merge(array0, i0 + 1, array1, i1, result, iR + 1);
    } else {
        result[iR] = array1[i1];
        return merge(array0, i0, array1, i1 + 1, result, iR + 1);
    }
}

A так стоит подумать, если там пачка меньших подряд идет в середине одного массива, а потом в другом и тд. Пока такой, самый простенький.
terranum
Рекурсия тут не очень подходит вот по этой причине:
public static void main(String[] args) {
        int[] a = new int[10000];
        System.out.println(Arrays.toString(merge(a, a)));
    }

Я бы немного урезал вот эту часть:

if(array0 == null && array1 == null)
        return null;
if(array0 == null)
        return array1;
    if(array1 == null)
        return array0;
if(array0.length == 0)
        return array1;
if(array1.length == 0)
        return array0;

Идея на счет вставки блоками звучит неплохо. Думаю будет интересно реализовать.
Airon
На счет рекурсии — с помощью -Xss можно ведь увеличить stack size, но все равно многовато сохраняет лишнего (все локальные переменные в стеке + то что return, и хотя они примитивы и ссылки, их все же много).
А на счет блоков:
public static int[] merge2(int[] array0, int[] array1) {
	if(array0 == null && array1 == null)
		return null;
	if(array0 == null)
		return array1;
	if(array1 == null)
		return array0;
	if(array0.length == 0)
		return array1;
	if(array1.length == 0)
		return array0;
	int[] result = new int[array0.length + array1.length];
	int i0 = 0,
	    i1 = 0,
	    iR = 0;
	while(iR < result.length) {
		int count = 0;
		if(array0[i0] < array1[i1]) {
			while((i0 + ++count) < array0.length && array0[i0 + count] <= array1[i1]);
			System.arraycopy(array0, i0, result, iR, count);
			if((i0 += count) >= array0.length) {
				System.arraycopy(array1, i1, result, iR + count, array1.length - i1);
				break;
			}
		} else {
			while((i1 + ++count) < array1.length && array1[i1 + count] <= array0[i0]);
			System.arraycopy(array1, i1, result, iR, count);
			if((i1 += count) >= array1.length) {
				System.arraycopy(array0, i0, result, iR + count, array0.length - i0);
				break;
			}
		}
		iR += count;
	}
	return result;
}

Но надо еще узнать где то/или у кого то, с какого размера начинается выгода System.arraycopy, есть подозрения что 1-3 лучше в лоб.
Sdu
  • Sdu
  • 0
Разъясните по заданию, момент «дополнительный массив не использовать». Объединив два массива мы получаем один новый, он не считается «дополнительным»? Другой вариант, мы добавляем содержимое одного исходного массива в другой исходный, но размерность то мы поменять тоже не можем.
Как понимать данный пункт условия?
terranum
Согласен «дополнительный массив не использовать» оказалось лишним. Один массив можно.
Olegator3
Так норм?

public static void main(String[] args)
    {
        int[] arr1 = {1,2,3,4,5};
        int[] arr2 = {5,6,7,8,9};
        System.out.println(Arrays.toString(newArray(arr1,arr2)));
    }
    private static int[] newArray(int[] arr1, int[] arr2)
    {
        if(arr1 == null && arr2 == null) return null;
        if(arr1 == null) return arr2;
        if(arr2 == null) return arr1;
        if(arr1.length == 0) return arr2;
        if(arr2.length == 0) return arr1;
        
        
       int[] result = new int[arr1.length + arr2.length];

        System.arraycopy(arr1,0,result,0,arr1.length);
        System.arraycopy(arr2,0,result,arr1.length,arr2.length);
        Arrays.sort(result);


        return result;
    }
}
terranum
Тут откровенный чит)
Arrays.sort(result);

Olegator3
исправим х)
terranum
Код рабочий, цель достигнута, по скорости написания в топе, так что не осмелюсь придраться. ;)
Olegator3
  • Olegator3
  • 0
  • Комментарий отредактирован 2015-01-21 01:55:50 пользователем Olegator3
И все же вот с сортировкой по Шенону, при не больших массивах должна лучше быть по-идее)
<code>
       private static int[] newArray(int[] arr1, int[] arr2)
    {
        if(arr1 == null && arr2 == null) return null;
        if(arr1 == null) return arr2;
        if(arr2 == null) return arr1;
        if(arr1.length == 0) return arr2;
        if(arr2.length == 0) return arr1;


       int[] result = new int[arr1.length + arr2.length];

        System.arraycopy(arr1,0,result,0,arr1.length);
        System.arraycopy(arr2,0,result,arr1.length,arr2.length);

       int h = 1;
        while(h * 3 < result.length)
            h = h * 3 + 1;

        while(h >= 1)
        {
            for(int i = h;i < result.length; i++)
            {
                for(int j = i; j >= h; j-=h)
                {
                    if(result[j] < result[j - h])
                    {
                        int tmp = result[j];
                        result[j] = result[j - h];
                        result[j - h] = tmp;
                    }
                    else break;
                }
            }
            h = h/3;
        }

        return result;
    }
}
</code>
iZulrad
public static int[] mergeArray(@NotNull int[] arr1, @NotNull int[] arr2) {
        if(arr1.length==0) return arr2;
        if(arr2.length==0) return arr1;

        int[] result = new int[arr1.length + arr2.length];
        int dex0 = 0;
        int dex1 = 0;
        int dex2 = 0;
        int lastDex1 = 0;
        int lastDex2 = 0;

        while (dex0 != result.length) {
            if (arr1[dex1] <= arr2[dex2]) {
                while (dex1 != arr1.length && arr1[dex1] <= arr2[dex2]) dex1++;
                System.arraycopy(arr1, lastDex1, result, dex0, dex1 - lastDex1);
                dex0 += (dex1 - lastDex1);
                lastDex1 = dex1;
            } else {
                while (dex2 != arr2.length && arr1[dex1] > arr2[dex2]) dex2++;
                System.arraycopy(arr2, lastDex2, result, dex0, dex2 - lastDex2);
                dex0 += (dex2 - lastDex2);
                lastDex2 = dex2;
            }

            if (dex1 == arr1.length) {
                System.arraycopy(arr2, lastDex2, result, dex0, arr2.length - dex2);
                break;
            }
            if (dex2 == arr2.length) {
                System.arraycopy(arr1, lastDex1, result, dex0, arr1.length - dex1);
                break;
            }
        }
        return result;
    }
iZulrad
Перемудрил)) Вот это побыстрее
public static int[] mergeArrays(@NotNull int[] arr1, @NotNull int[] arr2) {
        if (arr1.length == 0) return arr2;
        if (arr2.length == 0) return arr1;

        int[] result = new int[arr1.length + arr2.length];
        int dex1 = 0;
        int dex2 = 0;

        while (dex1 < arr1.length && dex2 < arr2.length) {
            if (arr1[dex1] <= arr2[dex2]) {
                result[dex1 + dex2] = arr1[dex1++];
            } else {
                result[dex1 + dex2] = arr2[dex2++];
            }
        }
        if (dex1 == arr1.length) {
            System.arraycopy(arr2, dex2, result, dex1 + dex2, arr2.length - dex2);
        } else {
            System.arraycopy(arr1, dex1, result, dex1 + dex2, arr1.length - dex1);
        }

        return result;
    }
iZulrad
public static int[] mergeArrays2(@NotNull int[] arr1, @NotNull int[] arr2) {
        int[] result = new int[arr1.length + arr2.length];
        int dex1 = 0, dex2 = 0;

        while (dex1 < arr1.length && dex2 < arr2.length)
            result[dex1 + dex2] = arr1[dex1] <= arr2[dex2] ? arr1[dex1++] : arr2[dex2++];

        if (dex1 == arr1.length) System.arraycopy(arr2, dex2, result, dex1 + dex2, arr2.length - dex2);
        else System.arraycopy(arr1, dex1, result, dex1 + dex2, arr1.length - dex1);

        return result;
    }
terranum
@NotNull понравилось, не знал о таком. Еще взял себе на заметку представление индекса result как dex1 + dex2. Красава!
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.