C#LeetCode刷题之#34-在排序数组中查找元素的第一个和最后一个位置（Find First and Last Position of Element in Sorted Array）

问题

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

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

输出: [3,4]

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

输出: [-1,-1]

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Input: nums = [5,7,7,8,8,10], target = 8

Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6

Output: [-1,-1]

示例

public class Program {

    public static void Main(string[] args) {

        var nums = new int[] { 2, 2 };

        var res = SearchRange(nums, 2);

        ShowArray(res);

        nums = new int[] { 5, 7, 7, 8, 8, 10 };

        res = SearchRange2(nums, 8);

        ShowArray(res);

        Console.ReadKey();

    }

    private static void ShowArray(int[] array) {

        foreach(var num in array) {

            Console.Write($"{num} ");

        }

        Console.WriteLine();

    }

    public static int[] SearchRange(int[] nums, int target) {

        //暴力线性

        var res = new int[] { -1, -1 };

        for(int i = 0, j = nums.Length - 1;

            i <= j && (res[0] == -1 || res[1] == -1);) {

            if(nums[i] == target) res[0] = i; else i++;

            if(nums[j] == target) res[1] = j; else j--;

        }

        return res;

    }

    public static int[] SearchRange2(int[] nums, int target) {

        //二分法

        var low = 0;

        var high = nums.Length - 1;

        var mid = 0;

        var res = new List<int>();

        while(low <= high) {

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

            if(nums[mid] == target) {

                var index = mid;

                while(index < high) {

                    if(nums[++index] != target) {

                        index--;

                        break;

                    }

                }

                res.Add(index);

                index = mid;

                while(index > 0) {

                    if(nums[--index] != target) {

                        index++;

                        break;

                    }

                }

                res.Insert(0, index);

                return res.ToArray();

            } else if(nums[mid] > target) {

                high = mid - 1;

            } else {

                low = mid + 1;

            }

        }

        res.Add(-1);

        res.Add(-1);

        return res.ToArray();

    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

0 1

3 4

分析：

显而易见，SearchRange 的时间复杂度为： $O(n)$ ，SearchRange2 的时间复杂度为： $O(logn)$ 。

巴特西

C#LeetCode刷题之#34-在排序数组中查找元素的第一个和最后一个位置（Find First and Last Position of Element in Sorted Array）

最新文章

热门文章