Блог

Вопрос ==> Вам даны два целых массива nums1 и nums2, отсортированных в неубывающем порядке, и два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.

Объедините nums1 и nums2 в один массив, отсортированный в неубывающем порядке.

Конечный отсортированный массив не должен быть возвращен функцией, а вместо этого должен храниться внутри массива nums1. Чтобы учесть это, nums1 имеет длину m n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов имеют значение 0 и должны игнорироваться. nums2 имеет длину n.

Что не так в моем коде???

     public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = 0; 
        int l = 0;
        for(int i=0; i<(m n); i  ){
            if(k > (m-1)){
                nums1[i] = nums2[l];
                l  = 1;
            }
            else if(nums1[k] <= nums2[l]){
                nums1[i] = nums1[k];
                k  = 1;
            }
            else {
                nums1[i] = nums2[l];
                l  = 1;
            }
        }
    }
}
 

Ваш вклад

 [1,2,3,0,0,0]
3
[2,5,6]
3
 

Мой вывод

 [1,2,2,2,5,6]
 

Ожидаемый результат

 [1,2,2,3,5,6]
 

Вы переопределяете значения в nums1 при объединении массивов, и таким образом вы заменяете некоторые числа из nums1, прежде чем проверять их на числа из nums2. В вашем примере, когда вы объединяетесь , есть момент, когда у вас есть i=2 , k=2 , l=0 и ваши nums1 выглядят следующим образом: nums1=[1,2,3,0,0,0] . До сих пор это выглядело хорошо , но теперь у вас есть nums1[k] ценность 3 и nums2[l] ценность 2 , поэтому вы устанавливаете nums1[i]=nums2[l] , т. Е. nums1[2]=nums2[0] . Таким образом, вы заменяете 3 на nums1 2 from nums2 , так что вы просто потеряли свой 3 оригинал из nums1 , и вы не сможете поместить его в окончательный массив.

Есть два решения этой проблемы:

1. Вспомогательный (временный) массив, в который вы поместите свои числа, и в конце концов этот массив будет объединен и отсортирован массивами nums1 и nums2, поэтому вы можете просто скопировать этот массив в nums1, чтобы все числа были объединены и отсортированы в nums1.
2. Каждый раз, когда вы помещаете число из nums2 в nums1 в i позицию, перемещайте все необработанные числа из исходного nums1 (числа из i позиции в последнее ненулевое число из nums1) на одну позицию вперед, чтобы ваш номер из i позиции сохранялся в i 1 позиции, номер из предыдущей i 1 позиции был в i 2 позиции и т.д. Просто соблюдайте правильный порядок перемещения этих чисел, т. Е. перемещайте их, начиная с последнего ненулевого числа и возвращаясь назад, чтобы избежать потери каких-либо чисел во время этого процесса.

Каждое из этих решений имеет свои преимущества и недостатки, связанные со сложностью времени и пространства, но в качестве примера я показываю, как реализовать первый подход:

 public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] mergedAndSortedArray = new int[m   n];
    int k = 0;
    int l = 0;
    for(int i=0; i<(m n); i  ){
        if(k > (m-1)){
            mergedAndSortedArray[i] = nums2[l];
            l  = 1;
        }
        else if(nums1[k] <= nums2[l]){
            mergedAndSortedArray[i] = nums1[k];
            k  = 1;
        }
        else {
            mergedAndSortedArray[i] = nums2[l];
            l  = 1;
        }
    }

    // copy final merged and sorted array to nums1, you can also do this using `for` loop but this is more efficient way
    System.arraycopy(mergedAndSortedArray, 0, nums1, 0, m   n);
}
 

Потому что в предложении if внутри цикла for вы, по сути, помещаете второй массив в конец первого, не проверяя, были ли уже использованы его номера.