88. Merge Sorted Array

题目：

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are mand n respectively.

链接： http://leetcode.com/problems/merge-sorted-array/

一刷，这道题写的太恶心了。因为python的for循环使用起来有限制，只能用在sequence上，我经常自己就固定在使用range

这道题经过的错误

1. line3-8没有检查，其中第8行后来还忘记return

2. idx_m, idx_n应该检查是否>=0，而非仅仅>0

3. line 20，检查>= 0

4. line 21的上边界要＋1

 1 class Solution(object):
 2     def merge(self, nums1, m, nums2, n):
 3         if n == 0:
 4             return
 5         if m == 0:
 6             for i in range(n):
 7                 nums1[i] = nums2[i]
 8             return
 9         idx_m = m - 1
10         idx_n = n - 1
11         for idx in range(m + n):
12             if idx_m >= 0 and idx_n >= 0:
13                 nums1[-idx - 1] = nums1[idx_m] if nums1[idx_m] > nums2[idx_n] else nums2[idx_n]
14                 if nums1[idx_m] > nums2[idx_n]:
15                     idx_m -= 1
16                 else:
17                     idx_n -= 1
18             else:
19                 break
20         if idx_n >= 0:
21             for idx in range(idx_n + 1):
22                 nums1[idx] = nums2[idx]

基本上前面这个解法是不能看的。

注意到nums1后面的下标是跟m, n同时变化的，可以减少一个变量来计算下标。注意line 4的条件判断和line 5是否过界

 1 class Solution(object):
 2     def merge(self, nums1, m, nums2, n):
 3 
 4         while m and n:
 5             if nums1[m - 1] > nums2[n - 1]:
 6                 nums1[m + n - 1] = nums1[m - 1]
 7                 m -= 1
 8             else:
 9                 nums1[m + n - 1] = nums2[n - 1]
10                 n -= 1
11         for i in range(n):
12             nums1[i] = nums2[i]

2/15/2017, Java

 1 public class Solution {
 2     public void merge(int[] nums1, int m, int[] nums2, int n) {
 3         int i = m - 1;
 4         int j = n - 1;
 5         int k = m + n - 1;
 6 
 7         for (; i >= 0 && j >= 0 && k >= 0; k--) {
 8             if (nums1[i] <= nums2[j]) {
 9                 nums1[k] = nums2[j];
10                 j--;
11             } else {
12                 nums1[k] = nums1[i];
13                 i--;
14             }
15         }
16         while (j >= 0) {
17             nums1[k] = nums2[j];
18             k--;
19             j--;
20         }
21     }
22 }