我遇到了一个需要在O(logn)时间复杂度内完成的面试问题。
给定一个已排序的整数数组和一个数字，找出该数字在数组中的起始和结束索引。
Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}
我试图找到一个高效的算法，但目前为止还没有成功。
6个回答
4
您可以使用二分查找的概念来找到起始和结束索引：
- 要找到起始索引，您将数组减半，如果值等于或大于输入数字，请重复使用数组的下半部分，否则请重复使用数组的上半部分。当您到达大小为1的数组时，请停止。 - 要找到结束索引，您将数组减半，如果值大于输入数字，请重复使用数组的下半部分，否则请重复使用数组的上半部分。当您到达大小为1的数组时，请停止。
请注意，当您到达大小为1的数组时，我们可能会在输入数字的旁边一个单元格，因此我们检查它是否等于输入数字，如果不是，则通过从我们找到的索引中添加/减少1来修正索引。
- 要找到起始索引，您将数组减半，如果值等于或大于输入数字，请重复使用数组的下半部分，否则请重复使用数组的上半部分。当您到达大小为1的数组时，请停止。 - 要找到结束索引，您将数组减半，如果值大于输入数字，请重复使用数组的下半部分，否则请重复使用数组的上半部分。当您到达大小为1的数组时，请停止。
请注意，当您到达大小为1的数组时，我们可能会在输入数字的旁边一个单元格，因此我们检查它是否等于输入数字，如果不是，则通过从我们找到的索引中添加/减少1来修正索引。
findStartIndex(int[] A, int num)
{
int start = 0; end = A.length-1;
while (end != start)
{
mid = (end - start)/2;
if (A[mid] >= num)
end = mid;
else
start = mid;
}
if(A[start] == num)
return start;
else
return start+1;
}
findEndIndex(int[] A, int num)
{
int start = 0; end = A.length-1;
while (end != start)
{
mid = (end - start)/2;
if (A[mid] > num)
end = mid;
else
start = mid;
}
if(A[start] == num)
return start;
else
return start-1;
}
整个过程如下：
int start = findStartIndex(A, num);
if (A[start]!=num)
{
print("-1,-1");
}
else
{
int end = findEndIndex(A, num);
print(start, end);
}
- Ron Teller
1
递归在这里是不必要的。 - Michał Rybak
2
听起来像是二分查找 -- 我记得对数图表示每次增加时的"折半"效果，基本上就是二分查找。
伪代码：
Set number to search for
Get length of array, check if number is at the half point
if the half is > the #, check the half of the bottom half. is <, do the inverse
repeat
if the half point is the #, mark the first time this happens as a variable storing its index
then repeat binary searches above , and then binary searches below (separately), such that you check for how far to the left/right it can repeat.
note*: and you sort binary left/right instead of just incrementally, in case your code is tested in a dataset with like 1,000,000 3's in a row or something
这个是否足够清晰，可以从这里开始吗？
- HC_
2
解决方案是同时（实际上不必并行:P）在开头对数组进行二分搜索。关键在于左侧和右侧的搜索略有不同。对于右侧，如果遇到重复项，则必须向右搜索；对于左侧，如果遇到重复项，则必须向左搜索。您要搜索的是边界，因此在右侧，您需要检查以下内容。
yournum, not_yournum
这是边界，左侧您只需朝相反方向搜索边界。最后返回边界的索引。
- aaronman
5
你是在建议使用线性搜索来查找重复项吗？但这样会导致运行时间取决于重复项的数量。我认为二分搜索可以自然地处理重复项，具体取决于你返回下限还是上限，尽管在这种情况下可能需要两个版本。 - Zong
@ZongZhengLi 不要读答案，每一步都涉及到数组的分割，没有线性搜索。 - aaronman
好的，我错了，你不仅建议进行第二次搜索，而且还建议进行第二次二分查找。那太不必要了，直接从一开始就使用第二个二分查找即可。 - Zong
@ZongZhengLi 哦，我想我可以删除第一个搜索。 - aaronman
@ZongZhengLi 第一个二分查找确实使算法更易读 - aaronman
0
可能是我的问题，但 Ron Teller 的答案在我测试时有一个无限循环。这里有一个在 Java 中的工作示例，如果您将 searchRange 函数更改为非静态函数，则可以在此处进行测试 here。
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class RangeInArray {
// DO NOT MODIFY THE LIST
public static ArrayList<Integer> searchRange(final List<Integer> a, int b) {
ArrayList<Integer> range = new ArrayList<>();
int startIndex = findStartIndex(a, b);
if(a.get(startIndex) != b) {
range.add(-1);
range.add(-1);
return range;
}
range.add(startIndex);
range.add(findEndIndex(a, b));
return range;
}
public static int findStartIndex(List<Integer> a, int b) {
int midIndex = 0, lowerBound = 0, upperBound = a.size() - 1;
while(lowerBound < upperBound) {
midIndex = (upperBound + lowerBound) / 2;
if(b <= a.get(midIndex)) upperBound = midIndex - 1;
else lowerBound = midIndex + 1;
}
if(a.get(lowerBound) == b) return lowerBound;
return lowerBound + 1;
}
public static int findEndIndex(List<Integer> a, int b) {
int midIndex = 0, lowerBound = 0, upperBound = a.size() - 1;
while(lowerBound < upperBound) {
midIndex = (upperBound + lowerBound) / 2;
if(b < a.get(midIndex)) upperBound = midIndex - 1;
else lowerBound = midIndex + 1;
}
if(a.get(lowerBound) == b) return lowerBound;
return lowerBound - 1;
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(1);
list.add(2);
list.add(2);
list.add(2);
list.add(2);
list.add(2);
list.add(2);
list.add(3);
list.add(4);
list.add(4);
list.add(4);
list.add(4);
list.add(5);
list.add(5);
list.add(5);
System.out.println("Calling search range");
for(int n : searchRange(list, 2)) {
System.out.print(n + " ");
}
}
}
- M. Irvin
0
由于还没有人发布可用的代码，我来发布一些（Java）：
public class DuplicateNumberRangeFinder {
public static void main(String[] args) {
int[] nums = { 0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9 };
Range range = findDuplicateNumberRange(nums, 3);
System.out.println(range);
}
public static Range findDuplicateNumberRange(int[] nums, int toFind) {
Range notFound = new Range(-1, -1);
if (nums == null || nums.length == 0) {
return notFound;
}
int startIndex = notFound.startIndex;
int endIndex = notFound.endIndex;
int n = nums.length;
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == toFind && (mid == 0 || nums[mid - 1] < toFind)) {
startIndex = mid;
break;
} else if (nums[mid] < toFind) {
low = mid + 1;
} else if (nums[mid] >= toFind) {
high = mid - 1;
}
}
low = 0;
high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == toFind && (mid == n - 1 || nums[mid + 1] > toFind)) {
endIndex = mid;
break;
} else if (nums[mid] <= toFind) {
low = mid + 1;
} else if (nums[mid] > toFind) {
high = mid - 1;
}
}
return new Range(startIndex, endIndex);
}
private static class Range {
int startIndex;
int endIndex;
public Range(int startIndex, int endIndex) {
this.startIndex = startIndex;
this.endIndex = endIndex;
}
public String toString() {
return "[" + this.startIndex + ", " + this.endIndex + "]";
}
}
}
- John Kurlak
0
双重二分查找。你从下标0开始，上标为长度减1。然后，你检查一半的点，并根据情况调整你的索引。
关键是，一旦找到目标，中心点将会分裂成两个中心点。
关键是，一旦找到目标，中心点将会分裂成两个中心点。
- SQB
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接