[LintCode/LeetCode] Merge Sorted Array

summerpxy 發布于2019-08-14 15:41 / 3555人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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