力扣00034.在排序数组中查找元素的第一个和最后一个位置

发表于 分类于 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 10 分钟
在排序数组中查找元素的第一个和最后一个位置、数组、二分查找、中等

题目描述

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 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 <= 10^5$
  • $-10^9 <= nums[i] <= 10^9$
  • nums 是一个非递减数组
  • $-10^9 <= target <= 10^9$

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        return {find_first_occurrence(nums, target), find_last_occurrence(nums, target)};
    }
private:
    int find_first_occurrence(const vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    int find_last_occurrence(const vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
};

结果

执行用时 : 10 ms, 击败 20.11% 使用 C++ 的用户

内存消耗 : 15.74 MB, 击败 6.25% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirstOccurrence(nums, target), findLastOccurrence(nums, target)};
    }
    private int findFirstOccurrence(int[] nums, int target) {
        int left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    private int findLastOccurrence(int[] nums, int target) {
        int left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 44.92 MB, 击败 12.98% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        def find_first_occurrence(nums, target):
            left, right, result = 0, len(nums) - 1, -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    result = mid
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return result
        def find_last_occurrence(nums, target):
            left, right, result = 0, len(nums) - 1, -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    result = mid
                    left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return result
        first_occurrence = find_first_occurrence(nums, target)
        last_occurrence = find_last_occurrence(nums, target)
        return [first_occurrence, last_occurrence]

结果

执行用时 : 14 ms, 击败 82.57% 使用 Python 的用户

内存消耗 : 11.77 MB, 击败 91.52% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def find_first_occurrence(nums, target):
            left, right, result = 0, len(nums) - 1, -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    result = mid
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return result
        def find_last_occurrence(nums, target):
            left, right, result = 0, len(nums) - 1, -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    result = mid
                    left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return result
        first_occurrence = find_first_occurrence(nums, target)
        last_occurrence = find_last_occurrence(nums, target)
        return [first_occurrence, last_occurrence]

结果

执行用时 : 32 ms, 击败 95.63% 使用 Python3 的用户

内存消耗 : 17.87 MB, 击败 30.78% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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] = find_first_occurrence(nums, numsSize, target);
    result[1] = find_last_occurrence(nums, numsSize, target);
    return result;
}
int find_first_occurrence(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}
int find_last_occurrence(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

结果

执行用时 : 5 ms, 击败 69.47% 使用 C 的用户

内存消耗 : 6.95 MB, 击败 99.07% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = FindFirstOccurrence(nums, target);
        result[1] = FindLastOccurrence(nums, target);
        return result;
    }
    private int FindFirstOccurrence(int[] nums, int target) {
        int left = 0, right = nums.Length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    private int FindLastOccurrence(int[] nums, int target) {
        int left = 0, right = nums.Length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

结果

执行用时 : 123 ms, 击败 70.95% 使用 C# 的用户

内存消耗 : 48.65 MB, 击败 5.24% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const findFirstOccurrence = function(nums, target) {
        let left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            let mid = left + Math.floor((right - left) / 2);
            if (nums[mid] === target) {
                result = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };
    const findLastOccurrence = function(nums, target) {
        let left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            let mid = left + Math.floor((right - left) / 2);
            if (nums[mid] === target) {
                result = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };
    const firstOccurrence = findFirstOccurrence(nums, target);
    const lastOccurrence = findLastOccurrence(nums, target);
    return [firstOccurrence, lastOccurrence];
};

结果

执行用时 : 48 ms, 击败 98.12% 使用 JavaScript 的用户

内存消耗 : 49.98 MB, 击败 8.48% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function searchRange(nums: number[], target: number): number[] {
    const findFirstOccurrence = function(nums: number[], target: number): number {
        let left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            let mid = left + Math.floor((right - left) / 2);
            if (nums[mid] === target) {
                result = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };
    const findLastOccurrence = function(nums: number[], target: number): number {
        let left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            let mid = left + Math.floor((right - left) / 2);
            if (nums[mid] === target) {
                result = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };
    const firstOccurrence = findFirstOccurrence(nums, target);
    const lastOccurrence = findLastOccurrence(nums, target);
    return [firstOccurrence, lastOccurrence];
}

结果

执行用时 : 65 ms, 击败 45.11% 使用 TypeScript 的用户

内存消耗 : 52.08 MB, 击败 14.82% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function searchRange($nums, $target) {
        return [$this->findFirstOccurrence($nums, $target), $this->findLastOccurrence($nums, $target)];
    }
    private function findFirstOccurrence($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;
        $result = -1;
        while ($left <= $right) {
            $mid = $left + intdiv(($right - $left), 2);
            if ($nums[$mid] === $target) {
                $result = $mid;
                $right = $mid - 1;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        return $result;
    }
    private function findLastOccurrence($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;
        $result = -1;
        while ($left <= $right) {
            $mid = $left + intdiv(($right - $left), 2);
            if ($nums[$mid] === $target) {
                $result = $mid;
                $left = $mid + 1;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        return $result;
    }
}

结果

执行用时 : 19 ms, 击败 87.10% 使用 PHP 的用户

内存消耗 : 21.48 MB, 击败 64.52% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        return [findFirstOccurrence(nums, target), findLastOccurrence(nums, target)]
    }
    private func findFirstOccurrence(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var result = -1
        while left <= right {
            let mid = left + (right - left) / 2
            if nums[mid] == target {
                result = mid
                right = mid - 1
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return result
    }
    private func findLastOccurrence(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var result = -1
        while left <= right {
            let mid = left + (right - left) / 2
            if nums[mid] == target {
                result = mid
                left = mid + 1
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return result
    }
}

结果

执行用时 : 14 ms, 击败 100.00% 使用 Swift 的用户

内存消耗 : 16.85 MB, 击败 5.10% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    fun searchRange(nums: IntArray, target: Int): IntArray {
        return intArrayOf(findFirstOccurrence(nums, target), findLastOccurrence(nums, target))
    }
    private fun findFirstOccurrence(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        var result = -1
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (nums[mid] == target) {
                result = mid
                right = mid - 1
            } else if (nums[mid] < target) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return result
    }
    private fun findLastOccurrence(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        var result = -1
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (nums[mid] == target) {
                result = mid
                left = mid + 1
            } else if (nums[mid] < target) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return result
    }
}

结果

执行用时 : 218 ms, 击败 48.00% 使用 Kotlin 的用户

内存消耗 : 38.01 MB, 击败 56.00% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  List<int> searchRange(List<int> nums, int target) {
    return [findFirstOccurrence(nums, target), findLastOccurrence(nums, target)];
  }
  int findFirstOccurrence(List<int> nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
      int mid = left + ((right - left) ~/ 2);
      if (nums[mid] == target) {
        result = mid;
        right = mid - 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return result;
  }
  int findLastOccurrence(List<int> nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
      int mid = left + ((right - left) ~/ 2);
      if (nums[mid] == target) {
        result = mid;
        left = mid + 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return result;
  }
}

结果

执行用时 : 302 ms, 击败 33.33% 使用 Dart 的用户

内存消耗 : 147.61 MB, 击败 66.67% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func searchRange(nums []int, target int) []int {
	return []int{findFirstOccurrence(nums, target), findLastOccurrence(nums, target)}
}
func findFirstOccurrence(nums []int, target int) int {
	left, right, result := 0, len(nums)-1, -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			result = mid
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return result
}
func findLastOccurrence(nums []int, target int) int {
	left, right, result := 0, len(nums)-1, -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			result = mid
			left = mid + 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return result
}

结果

执行用时 : 4 ms, 击败 89.67% 使用 Go 的用户

内存消耗 : 4.32 MB, 击败 78.50% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def search_range(nums, target)
  [find_first_occurrence(nums, target), find_last_occurrence(nums, target)]
end
def find_first_occurrence(nums, target)
  left, right, result = 0, nums.length - 1, -1
  while left <= right
    mid = left + (right - left) / 2
    if nums[mid] == target
      result = mid
      right = mid - 1
    elsif nums[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end
  result
end
def find_last_occurrence(nums, target)
  left, right, result = 0, nums.length - 1, -1
  while left <= right
    mid = left + (right - left) / 2
    if nums[mid] == target
      result = mid
      left = mid + 1
    elsif nums[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end
  result
end

结果

执行用时 : 60 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.79 MB, 击败 66.67% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
object Solution {
  def searchRange(nums: Array[Int], target: Int): Array[Int] = {
    Array(findFirstOccurrence(nums, target), findLastOccurrence(nums, target))
  }
  def findFirstOccurrence(nums: Array[Int], target: Int): Int = {
    var left = 0
    var right = nums.length - 1
    var result = -1
    while (left <= right) {
      val mid = left + (right - left) / 2
      if (nums(mid) == target) {
        result = mid
        right = mid - 1
      } else if (nums(mid) < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
    result
  }
  def findLastOccurrence(nums: Array[Int], target: Int): Int = {
    var left = 0
    var right = nums.length - 1
    var result = -1
    while (left <= right) {
      val mid = left + (right - left) / 2
      if (nums(mid) == target) {
        result = mid
        left = mid + 1
      } else if (nums(mid) < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
    result
  }
}

结果

执行用时 : 549 ms, 击败 10.00% 使用 Scala 的用户

内存消耗 : 59.05 MB, 击败 10.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        vec![Self::find_first_occurrence(&nums, target), Self::find_last_occurrence(&nums, target)]
    }
    fn find_first_occurrence(nums: &Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len() as i32 - 1;
        let mut result = -1;
        while left <= right {
            let mid = left + (right - left) / 2;
            if nums[mid as usize] == target {
                result = mid;
                right = mid - 1;
            } else if nums[mid as usize] < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        result
    }
    fn find_last_occurrence(nums: &Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len() as i32 - 1;
        let mut result = -1;
        while left <= right {
            let mid = left + (right - left) / 2;
            if nums[mid as usize] == target {
                result = mid;
                left = mid + 1;
            } else if nums[mid as usize] < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        result
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.28 MB, 击败 75.00% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(define/contract (search-range nums target)
  (-> (listof exact-integer?) exact-integer? (listof exact-integer?))
  (define (find-first-occurrence nums target left right)
    (cond
      ((> left right) -1)
      (else
       (let ((mid (quotient (+ left right) 2)))
         (cond
           ((= (list-ref nums mid) target)
            (let ((first-left (find-first-occurrence nums target left (- mid 1))))
              (if (= first-left -1) mid first-left)))
           ((< (list-ref nums mid) target)
            (find-first-occurrence nums target (+ mid 1) right))
           (else
            (find-first-occurrence nums target left (- mid 1))))))))
  (define (find-last-occurrence nums target left right)
    (cond
      ((> left right) -1)
      (else
       (let ((mid (quotient (+ left right) 2)))
         (cond
           ((= (list-ref nums mid) target)
            (let ((last-right (find-last-occurrence nums target (+ mid 1) right)))
              (if (= last-right -1) mid last-right)))
           ((< (list-ref nums mid) target)
            (find-last-occurrence nums target (+ mid 1) right))
           (else
            (find-last-occurrence nums target left (- mid 1))))))))
  (list (find-first-occurrence nums target 0 (- (length nums) 1))
        (find-last-occurrence nums target 0 (- (length nums) 1))))

结果

执行用时 : 214 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 98.83 MB, 击败 100.00% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户