Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merge Sorted Array #17

Open
xuexueq opened this issue Sep 25, 2018 · 0 comments
Open

Merge Sorted Array #17

xuexueq opened this issue Sep 25, 2018 · 0 comments
Labels
leetcode_easy leetcode_easy 数据结构与算法 数据结构与算法

Comments

@xuexueq
Copy link
Owner

xuexueq commented Sep 25, 2018

Merge Sorted Array

题目描述:合并两个有序的数组

地址:https://leetcode.com/problems/merge-sorted-array/description/

限定条件:不允许使用遍历或者 sort 方法

思路:

合并后的数组总的有效数目为m+n,因为都是从0开始,所以nums1和nums2的最后一个元素的索引分别是m-1和n-1,合并后的nums1的最后一个元素的索引应该是m+n-1。

依次对数组 nums1 尾部(即从确定大数开始)和 nums2 尾部(最大数)进行比较,大的那一个数移除并去填补新数组的尾部。

// 把 arr2 合并到 arr1 中
function merge(arr1, arr2) {
    let len1 = arr1.length;
    let len2 = arr2.length;
    let i = len1 - 1;
    let j = len2 - 1;
    let position = len1 + len2 - 1;
    while(j >= 0 && i >= 0) {
        arr1[position--] = arr1[i] > arr2[j] ? arr1[i--] : arr2[j--];
    }
    return arr1;
}
merge([1,4,5],[1,2,8,9])
@xuexueq xuexueq added 数据结构与算法 数据结构与算法 leetcode_easy leetcode_easy labels Sep 25, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
leetcode_easy leetcode_easy 数据结构与算法 数据结构与算法
Projects
None yet
Development

No branches or pull requests

1 participant