在本文中,我们将研究与搜索算法相关的编码面试中提出的一个有趣问题。问题是:Given a Sorted Array, we need to find the first and last position of an element in Sorted array。Search for a range这个问题在 Leetcode 上也被称为。我们将研究解决问题的不同方法及其实施,并分析我们方法的复杂性。
Given a Sorted Array, we need to find the first and last position of an element in Sorted array
Search for a range
基本上,我们需要确定Array中重复键元素的第一次和最后一次出现。例如考虑这个数组:
具有重复元素的排序数组。
在这里,我们可以看到一个大小为 10 的数组,其中包含重复的元素 5 和 7。如果我们想知道元素 5 的第一次和最后一次出现,它将分别位于索引 3 和 4。类似地,对于元素 7,第一次和最后一次出现分别位于位置/索引 5 和 7。
Input: Array = {2,3,4,5,5,7,7,7,9,11}, target = 7 Output: 5,7 // Comma separated Index of First and Last Occurrence. Input: Array = {5,6,6,6,7,8,8,10}, target = 8 Output: 5,6
现在让我们看看我们解决这个问题的方法。
在此方法中,我们将遵循以下步骤:
让我们看一下这个方法的代码:
import java.util.*; public class Example { static void findFirstAndLastPosition(int arr[],int n,int target) { // We initialize first and last as -1 if the target is not present in the array. int first = -1; int last = -1; for(int i=0;i<n;i++) { if(arr[i] == target) { first = i; break; } } for(int i=n-1;i>=0;i--) { if(arr[i] == target) { last = i; break; } } System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last); } public static void main(String args[]) { int arr[] = new int[]{2,3,4,5,5,7,7,7,9,11}; int n = arr.length; int target = 7; findFirstAndLastPosition(arr,n,target); } }
Output:
The First occurrence of 7 at index : 5 and the Last occurrence is at index : 7
Time Complexity:在这里,如果第一次出现在倒数第二个元素,我们执行线性搜索来获取索引,那么我们必须遍历整个数组。因此,整体运行时间为O(n).
Time Complexity:
O(n)
这种方法的想法或目的是通过使用和修改二分搜索算法来最小化上述方法的运行时间。这种方法的分解如下所示:
findStartingIndex(Array,target)
findEndingIndex(Array,target)
现在,对于
findStartingIndex()
方法,我们将通过执行修改后的二进制搜索来搜索目标。我们计算
mid = (low + high) / 2
(low = 0 and high = Array_Size – 1)。随着数组的排序,对于 mid 的每个值,我们需要根据三个条件执行操作。
If(Arr[mid] >= target)
high = mid - 1
low = mid + 1
If(Arr[mid] == target)
同样对于
findEndingIndex()
方法,我们通过进行一些更改来搜索目标。该算法与上面讨论的方法保持相同,只是需要更改条件。
If(Arr[mid] <= target)
high = mid -1
low<=high
让我们看一下上述方法的实现:
import java.util.*; public class Example { //finds Starting Index or First occurrence of target. static int findStartingIndex(int arr[],int n,int target) { int low = 0; int high = n-1; int index = -1; while(low <= high) { // Calculate mid value. int mid = (low+high)/2; //Condition 1 if(arr[mid]>=target) { high = mid-1; } // Condition 2 : When arr[mid] < target else { low = mid+1; } // Condition 3 if(arr[mid] == target) { index = mid; } } return index; } //finds Last occurrence of target. static int findEndingIndex(int arr[],int n,int target) { int low = 0; int high = n-1; int index = -1; while(low <= high) { // Calculate mid value. int mid = (low+high)/2; //Condition 1 if(arr[mid]<=target) { low = mid+1; } // Condition 2 : When arr[mid] > target else { high = mid-1; } // Condition 3 if(arr[mid] == target) { index = mid; } } return index; } static void findFirstAndLastPosition(int arr[],int n,int target) { int first = findStartingIndex(arr,n,target); int last = findEndingIndex(arr,n,target); System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last); } public static void main(String args[]) { int arr[] = new int[]{5,6,6,6,7,8,8,10}; int n = arr.length; int target = 8; findFirstAndLastPosition(arr,n,target); } }
The First occurrence of 8 at index : 5 and the Last occurrence is at index : 6
时间复杂度:我们使用二分搜索来获取目标元素的第一次和最后一次出现。我们知道二分查找的运行时间为 O(log n)。此后,对 findStartingIndex() 和 findEndingIndex() 方法的调用分别花费 O(log n) 时间。因此,整体复杂度为 O(log n + log n) = O(log n)。这是解决此问题的最佳方法。
O(log n)
这就是搜索范围 Leetcode 的全部内容——在有序数组中查找元素的第一个和最后一个位置。
原文链接:https://codingdict.com/