LeetCode如何在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

一，在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

1，問題描述

給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

2，示例描述

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]
示例 2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]
示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]
 

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一個(gè)非遞減數(shù)組
-109 <= target <= 109

 

3，題解思路

本題基于我們最熟悉的集合LinkedHashMap鍵值對(duì)集合來做

4，題解程序

import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class SearchRanageTest2 {
    public static void main(String[] args) {
        int[] nums = {3, 3, 3};
        int target = 3;
        
        int[] searchRange = searchRange(nums, target);
        for (int num : searchRange) {
            System.out.print(num + "\t");
        }
    }

    public  static  int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }

        Map<Integer, Integer> map = new LinkedHashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            map.put(i, nums[i]);
        }
        
        List<Map.Entry<Integer, Integer>> collect = map
            .entrySet()
            .stream()
            .filter(x -> x.getValue() == target)
            .collect(Collectors.toList());
        
        if (collect.size() == 0) {
            return new int[]{-1, -1};
        }
        
        if (collect.size() == 1) {
            return new int[]{collect.get(0).getKey(), collect.get(0).getKey()};
        }
   
        if (collect.size() > 2) {
            return new int[]{collect.get(0).getKey(), collect.get(collect.size() - 1).getKey()};
        }
        
        int[] result = new int[collect.size()];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : collect) {
            result[index++] = entry.getKey();
        }
      
        return result;
    }
}