At the end of the exam, the average score of the class only got the second grade, the teacher in charge then asked: everyone knows the world’s first peak Qomolangma, anyone know the world’s second peak is what? Just as the teacher was going to continue to speak, he heard a voice in the corner: “K2”
preface
2018.11.16 punch in tomorrow’s topic leetcode66: https://leetcode-cn.com/problems/plus-one/
The title
Leetcode88 – Merge two ordered array categories: linked list https://leetcode-cn.com/problems/merge-sorted-array/ link to https://leetcode.com/problems/merge-sorted-array/ in English
Detailed questions
Given two ordered integer arrays nums1 and nums2, merge nums2 into nums1 such that num1 becomes an ordered array. Note: The number of elements initialized for nums1 and nums2 is m and N, respectively. You can assume that NUMs1 has enough space (space size greater than or equal to m + n) to hold elements in NUMs2. Example: input: nums1 =,2,3,0,0,0 [1], m = 3 nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1]
The title,
The idea of using extra space
- Mix insert ordered array, since both arrays are ordered, so as long as the order of the size can be compared. The first idea is to create A new array of m+ N size, and then compare the elements from array A and array B one by one, add the smaller elements to the new array, and then consider the two cases that array A has surplus and array B has surplus, and finally reassign the elements of the new array to array A.
code
1class Solution {
2 public void merge(int[] nums1, int m, int[] nums2, int n) {
3 int [] result = new int[m+n];
4 int i =0,j=0,k=0;
5 while(i < m && j < n)
6 {
7 if(nums1[i] < nums2[j]){
8 result[k++] = nums1[i++];
9 }else{
10 result[k++] = nums2[j++];
11 }
12 }
13 if(i ! = m)
14 {
15 while(i < m)
16 {
17 result[k++] = nums1[i++];
18 }
19 }
20 if(j ! = n)
21 {
22 while(j < n)
23 {
24 result[k++] = nums2[j++];
25 }
26 }
27 k = 0;
28 for(i=0; i<nums1.length; i++)
29 nums1[i] = result[k++];
30
31 }
32}
Copy the codeThe code on
- Select * from num1; select * from nums2
- Lines 13-26 are two arrays, one of which may not be iterated, so add the iterated array to the result array
- Lines 28-29 copy the result array into nums1.
The idea of not using extra space
- Since the size of the array A must be m+n, the assignment starts from the very end, compares the size of the last element in A and B, inserts the larger one at m+n-1, and then pushes forward. If all the elements in A are smaller than B, then the first m are the same as A was, unchanged. If the array in A is larger than the array in B, when A is done, and there are elements in B that haven’t been added to A, just loop over all the elements in B to the rest of A.
code
1class Solution {
2 public void merge(int[] nums1, int m, int[] nums2, int n) {
3 int k = m + n - 1;
4 int i = m- 1;int j = n- 1;
5 while(i >=0 && j >= 0)
6 {
7 if(nums1[i] > nums2[j])
8 {
9 nums1[k--] = nums1[i--];
10 }else{
11 nums1[k--] = nums2[j--];
12 }
13 }
14 if(i > 0)
15 {
16 while(i >= 0)
17 {
18 nums1[k--] = nums1[i--];
19 }
20 }
21 if(j >= 0)
22 {
23 while(j >= 0)
24 {
25 nums1[k--] = nums2[j--];
26 }
27 }
28 }
29}
Copy the codeThe code on
- Lines 5-13 start at the end of nums1 and nums2, and store the largest nums1 after nums1.
- Line 14-20: If nums1 is not iterated, keep nums1 in nums1. This code is not necessary because nums1 is sorted and does not need to be duplicated.
- Line 21-27: If nums2 is not iterated, copy nums2 to nums1. This is mandatory because nums2 is not nums1.
conclusion
# 2018.11.16 clock
Author Chowgory experienced the autumn admission of 2019. He is a computer master of Harbin Institute of Technology and a Java engineer admitted to Baidu. Welcome to follow my wechat official account: The official account has 3T programming resources, and my friend and I (admitted baidu C++ engineer) prepared nearly 200 MB of required interview Java and C++ experience during the autumn recruitment, and there is a leetcode punch card group and technical exchange group every day, welcome to follow.