Итак, вчера мы задали этот вопрос, но Сони нашел один пограничный случай, а я нашел другой, но решение было очень плохим, как будто мы что-то забыли, но после обсуждения мы поняли, как мы будем его решать.
You are given two integer arraysnums1
andnums2
, sorted in non-decreasing order, and two integersm
andn
, representing the number of elements innums1
andnums2
respectively. Mergenums1
andnums2
into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the arraynums1
. To accommodate this,nums1
has a length ofm + n
, where the firstm
elements denote the elements that should be merged, and the lastn
elements are set to0
and should be ignored.nums2
has a length ofn
. Example 1: Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Теперь Сони использовал указатели для поиска решения, но он упустил порядок, в котором мы будем проходить массив, тогда как я полностью сосредоточился на обратном направлении, но забыл об указателях. Итак, ниже мои заметки
Ниже приведено оптимальное решение, нам нужно двигаться в обратном направлении, потому что мы знаем, что общая длина nums1 = n + m.
Мы говорили о слиянии решения, но в то время не кодировали, сегодня я посмотрел, как мы можем решить это обратным способом. Мне нравится этот вопрос, очень простой, но тот факт, что мы обычно не смотрим в противоположном направлении для обхода, на самом деле не открывает других взглядов на его решение.