资讯专栏INFORMATION COLUMN

[LintCode/LeetCode] Merge Sorted Array

summerpxy / 3543人阅读

Problem

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

Notice

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 m and n respectively.

Example

A = [1, 2, 3, empty, empty], B = [4, 5]

After merge, A will be filled as [1, 2, 3, 4, 5]

Tags

Sorted Array Array Facebook

Solution
    class Solution {
        public void mergeSortedArray(int[] A, int m, int[] B, int n) {
            int index = m+n-1, i = m-1, j = n-1;
            while (i >= 0 && j >= 0) {
                if (A[i] > B[j]) A[index--] = A[i--];
                else A[index--] = B[j--];
            }
            while (i >= 0) A[index--] = A[i--];
            while (j >= 0) A[index--] = B[j--];
        }
    }

some weird solution...

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1, j = n-1, k = m+n-1;
        while (k >= 0) {
            if (i >= 0 && j >= 0 && nums1[i] >= nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else if (i >= 0 && j >= 0 && nums1[i] < nums2[j]) {
                nums1[k] = nums2[j];
                j--;
            } else if (i < 0 && j >= 0) {
                nums1[k] = nums2[j];
                j--;
            } else {
                return;
            }
            k--;
        }
        return;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/65943.html

相关文章

  • [LintCode/LeetCode] Merge Two Sorted Lists

    摘要:先考虑和有无空集,有则返回另一个。新建链表,指针将和较小的放在链表顶端,然后向后遍历,直到或之一为空。再将非空的链表放在后面。 Problem Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splici...

    dockerclub 评论0 收藏0
  • [LintCode/LeetCode] Remove Duplicates from Sorted

    摘要:思路原数组长度为,则返回原数组长度不为,则至少有个元素。将所有不重复的数值赋给,而当和相等时,不做处理。最后返回的就是不同元素的个数,也是新数组的长度。只有在时,才对赋值。注意,每次初始化的时候要分两种情况,这就意味着从的时候开始遍历。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...

    WalkerXu 评论0 收藏0
  • [LintCode/LeetCode] Find Minimum in Rotated Sorted

    摘要:排序数组中找最小值或最大值的题目,很明显可以使用二分法。因此,只判断终点和中点元素的大小关系即可。这里有一种情况是上述后三个,中点值和末位相等。此时,两边同时递归,并返回两边递归值的较小值。当首位和末位重合,说明已夹逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

    cgh1999520 评论0 收藏0
  • [LintCode/LeetCode] Search in Rotated Sorted Arra

    摘要:找中点若起点小于中点,说明左半段没有旋转,否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无,就容易了。还是用二分法优化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...

    U2FsdGVkX1x 评论0 收藏0
  • [LintCode/LeetCode] Find Median From / Data Stream

    摘要:建立两个堆,一个堆就是本身,也就是一个最小堆另一个要写一个,使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里,更大的数放在最小堆,较小的数放在最大堆。同时,确保最大堆的比最小堆大,才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

    zxhaaa 评论0 收藏0

发表评论

0条评论

summerpxy

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<