欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array(C语言)

程序员文章站 2024-03-17 15:52:10
...

题目描述:

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

题目解答:

方法1:二分法

利用二分法先找到等于target的位置,然后从这个位置向两边遍历找第一个和最后一个。但这种方式不一定是O(log n),可以进行优化。
运行时间4ms,代码如下。

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 2;
    result[0] = -1;
    result[1] = -1;
    int left = 0, right = numsSize - 1, mid = 0;
    while(left <= right) {
        mid = (left + right) / 2;
        if(nums[mid] == target) {
            left = mid - 1;
            right = mid + 1;
            while(left >= 0 && nums[left] == target)
                left--;
            while(right < numsSize && nums[right] == target)
                right++;
            result[0] = left + 1;
            result[1] = right - 1;
            return result;
        }
        else if(nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;   
    } 
    return result;
}

优化方法:先用二分法找到最左边与目标数相等的位置,再用二分法找到最右边与目标数相等的位置。
运行时间4ms,代码如下。

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 2;
    result[0] = -1;
    result[1] = -1;
    int left = 0, right = numsSize - 1, mid = 0;
    while(left <= right) {
        mid = (left + right) / 2;
        if(nums[mid] >= target)
            right = mid - 1;
        else
            left = mid + 1;   
    } 
    if(left == numsSize || nums[left] != target)
        return result;
    result[0] = left;
    
    left = 0;
    right = numsSize - 1;
    while(left < right) {
        mid = (left + right) / 2 + 1;
        if(nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;   
    } 
    if(nums[right] > target)
        right--;
    result[1] = right;
    return result;
}
相关标签: 二分法 C语言