[LintCode/LeetCode] Merge Sorted Array

summerpxy 发布于2019-08-14 15:41 / 3534人阅读

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;
    }
}

GPU云服务器云服务器 sorted-array array_merge() array_merge Sorted

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

转载请注明本文地址：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 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Remove Duplicates from Sorted

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

WalkerXu 2019-08-14 15:32 评论0 收藏0
[LintCode/LeetCode] Find Minimum in Rotated Sorted

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

cgh1999520 2019-08-14 15:22 评论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 2019-08-14 15:41 评论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 2019-08-14 14:35 评论0 收藏0