嘿,我在采访中有这个问题,想知道什么是解决这个问题的最佳方法。所以说给你一个已经排序的数组,你想找到某个值x的最低索引。
Hey I had this question in an interview and was wondering what was the best way to solve it. So say you are given an array that is already sorted and you want to find the lowest index of some value x.
这是我想出的python / pseudocode与,我只是想知道是否还有更好的方法?
Here is a python/pseudocode of what I came up with, I am just wondering if there is a better way to go about it?
def findLowestIndex(arr, x): index = binarySearch(0, len(arr), x) if index != -1: while index > 0: if arr[index] == arr[index-1]: index -= 1 else: break return index谢谢!
推荐答案在最坏的情况下,即数组中 x s的计数为O( n )时,您的方法会花费线性时间。
Your method takes linear time in the worst case, which is when the count of xs in the array is O(n).
可以通过更改二进制搜索本身以找到第一个 x $来获得O(lg n )解决方案c $ c>而不是数组中的任何一个:
An O(lg n) solution can be obtained by changing the binary search itself to find the first x in the array instead of just any one of them:
def binary_search(x, a): lo = 0 hi = len(a) while lo < hi: mid = (lo + hi) // 2 if a[mid] < x: lo = mid + 1 elif a[mid] > x: hi = mid elif mid > 0 and a[mid-1] == x: hi = mid else: return mid return -1更多推荐
在预排序数组中找到给定值的最低索引
发布评论