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

28 уровень

18.01.2015
2112просмотров
16комментариев

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

участников

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

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

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

iZulrad

Уровень 34

21 января 2015, 11:54

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, 18:34

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

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, 19:44

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, 23:08

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

Olegator3

Уровень 37

21 января 2015, 01:55

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

<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, 00:55

Так норм?


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, 01:25

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

Arrays.sort(result);

Olegator3

Уровень 37

21 января 2015, 01:31

исправим х)

terranum

Уровень 28

21 января 2015, 01:33

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

terranum

Уровень 28

20 января 2015, 23:14

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

Sdu

Уровень 17

20 января 2015, 22:34

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

terranum

Уровень 28

20 января 2015, 22:13

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

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, 00:44

На счет рекурсии — с помощью -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, 12:03

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

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, 23:41

Правила тут

kolust

Уровень 40

18 января 2015, 21:30

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