leedcode 排序和搜索

链接

合并两个有序数组

题目说明

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

题目解析

没什么好说的。

代码

#include <stdlib.h>
#include <memory.h>

//合并两个有序数组
void merge(int *nums1, int nums1Size, int m, int *nums2, int nums2Size, int n)
{
    //将num1中的数据转移到temp中。
    //temp1指向num1等价数据区 temp2指向num2 res指向目标
    int * temp1=(int *)malloc(m*sizeof(int));
    int *temp2 =nums2;
    int *res=nums1;
    int *end1=temp1+m;
    int *end2=temp2+n;
    memcpy(temp1,nums1,m*sizeof(int));
    while(temp1!=end1&&temp2!=end2)
    {
        *(res++)=*temp1<=*temp2?(*temp1++):(*temp2++);
    }
    if(temp1==end1)
        memcpy(res,temp2,(end2-temp2)*sizeof(int));
    else 
        memcpy(res,temp1,(end1-temp1)*sizeof(int));
}

第一个错误的版本

题目描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数

题目解析

二分查找即可，注意二分时超出int的范围。可以使用一下方法防止超出范围。

1	int mid=low+(high-low)/2;

代码

int firstBadVersion(int n)
{
    int begin=1;
    int end=n;
    while(begin<end)
    {
        int mid=begin+(end-begin)/2;
        if(isBadVersion(mid))
            end=mid;
        else 
            begin=mid+1;
    }
    return begin;
}