Given a sorted arrays with integers and a target to locate, find the first and last position of the element in the sorted array.
Example: Input: nums = [5,7,7,8,8,10], target = 8, Output: [3, 4]
Example: Input: nums = [5,7,7,8,8,10], target = 6, Output: [-1, -1]
The string object in Javascript has two methods indexOf and lastIndexOf which can be used to solve this problem – without taking advantages of the fact that the array is sorted:
1 2 3 4 5 6 7 8 | /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange = function(nums, target) { return [nums.indexOf(target), nums.lastIndexOf(target)]; }; |
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
return [nums.indexOf(target), nums.lastIndexOf(target)];
};C++ indexOf and lastIndexOf Implementation
Let’s put aside the sorted characteristic, we can search from both sides and the complexity is O(N).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int a = -1, b = -1; for (int i = 0; i < nums.size(); ++ i) { if (nums[i] == target) { a = i; break; } } for (int i = nums.size() - 1; i >= 0; --i) { if (nums[i] == target) { b = i; break; } } return {a, b}; } }; |
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int a = -1, b = -1;
for (int i = 0; i < nums.size(); ++ i) {
if (nums[i] == target) {
a = i;
break;
}
}
for (int i = nums.size() - 1; i >= 0; --i) {
if (nums[i] == target) {
b = i;
break;
}
}
return {a, b};
}
};Since the array is sorted, we can use the binary search to reduce to complexity to O(logN) in average cases. We locate the target element and use the sliding window to determine the first and last position. However, if the array contains all duplicate numbers, the algorithm will degrade to O(N).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int low = 0, high = nums.size() - 1, mid; int lower = -1, higher = -1; while (low <= high) { mid = low + (high - low) / 2; if (target > nums[mid]) { low = mid + 1; } else if (target < nums[mid]) { high = mid - 1; } else { lower = mid; higher = mid; break; } } if (lower == -1) return {-1, -1}; while (lower > 0 && nums[lower] == nums[lower - 1]) lower--; while (higher + 1 < nums.size() && nums[higher] == nums[higher + 1]) higher ++; return {lower, higher}; } }; |
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1, mid;
int lower = -1, higher = -1;
while (low <= high) {
mid = low + (high - low) / 2;
if (target > nums[mid]) {
low = mid + 1;
} else if (target < nums[mid]) {
high = mid - 1;
} else {
lower = mid;
higher = mid;
break;
}
}
if (lower == -1) return {-1, -1};
while (lower > 0 && nums[lower] == nums[lower - 1]) lower--;
while (higher + 1 < nums.size() && nums[higher] == nums[higher + 1]) higher ++;
return {lower, higher};
}
};–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: The Javascript Function to Check Any Two Sets Are the Same
Next Post: How to Perform the Case Insensitive Palindrome String Tests in C++?
