JavaRush /Java блог /Архив info.javarush /Кухня(); Второй сезон - 72/79

28 уровень

Milan

18 января 2015
2455 views
16 comments

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

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

Комментарии (16)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

iZulrad Уровень 34

21 января 2015

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 Уровень 34

21 января 2015

Перемудрил)) Вот это побыстрее

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 Уровень 34

21 января 2015

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 Уровень 28

21 января 2015

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

Olegator3 Уровень 37

21 января 2015

И все же вот с сортировкой по Шенону, при не больших массивах должна лучше быть по-идее)

<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>

Olegator3 Уровень 37

21 января 2015

Так норм?


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 Уровень 28

21 января 2015

Тут откровенный чит)

Arrays.sort(result);

Olegator3 Уровень 37

21 января 2015

исправим х)

terranum Уровень 28

21 января 2015

Код рабочий, цель достигнута, по скорости написания в топе, так что не осмелюсь придраться. ;)

terranum Уровень 28

20 января 2015

Согласен «дополнительный массив не использовать» оказалось лишним. Один массив можно.

Sdu Уровень 17

20 января 2015

Разъясните по заданию, момент «дополнительный массив не использовать». Объединив два массива мы получаем один новый, он не считается «дополнительным»? Другой вариант, мы добавляем содержимое одного исходного массива в другой исходный, но размерность то мы поменять тоже не можем.
Как понимать данный пункт условия?

terranum Уровень 28

20 января 2015

Рекурсия тут не очень подходит вот по этой причине:

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 Уровень 34

21 января 2015

На счет рекурсии — с помощью -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 лучше в лоб.

Airon Уровень 34

20 января 2015

"(дополнительный массив не использовать)"?

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 Уровень 28

18 января 2015

Правила тут

kolust Уровень 40

18 января 2015

А в чем собственно проблема???