spi*_*kus 31
这是Python中的O(n)一次通过解决方案.端口到Java是微不足道的:
import random
A = [random.randint(1, 10) for i in range(0, 5)] # Generate list of size 5.
max_seen = A[0]
candidate = None
for i in range(1,len(A)):
if candidate is None:
if A[i] > max_seen:
candidate = i
else:
if A[i] <= A[candidate]:
candidate = None
max_seen = max(max_seen, A[i])
print("Given %s " % (A,))
if candidate is not None and candidate != len(A)-1: # Ignore the last element as per spec.
print("found: value=%d; index=%d\n" % (A[candidate], candidate))
else:
print("not found")
您需要运行几次以生成实际满足条件的列表.
描述
重述目标:找到数组A中元素的索引i,使得所有A [j],j <i => A [j] <A [i]和所有A [k],k> i => A [k ]> A [i].第一个这样的元素是一个这样的元素,所以我们只找到第一个元素.
给定索引x,如果x满足上述条件,则A [x]> A [0..x-1]和A [x] <A [x + 1..A.length].验证给定x的两个约束就足够了.注A [x]> A [0..x-1] <=> A [x]> max(A [0..x-1]).因此,我们保持到目前为止看到的最大值,找到满足条件1 的第一个x,并遍历数组验证条件2.如果条件2未被验证,我们知道下一个可能的候选者超出当前索引y,因为A [x..y-1]> A [x] => A [y] <A [x..y-1 ],并且大于目前为止看到的最大值.
pax*_*blo 16
是的,它当然可以及时完成O(n).接下来是几种方法.
第一个对于找到所有候选细胞更有用.单个O(n)传递数据设置每个单元格两个额外的项目,因此O(n)空间(通过交易空间的时间可以解决非平凡数量的优化问题).
您需要为每个单元格计算的两个项目是左侧的最高值和右侧的最小值.第一个通道为所有单元格设置这些项目,最后选择一个没有意义的单元格(显然是伪代码):
# Set current values.
highLeftVal = cell[0]
lowRightVal = cell[cell.lastIndex]
# For running right and left through array.
rightIdx = cell.lastIndex
for each leftIdx 1 thru cell.lastIndex inclusive:
# Left index done by loop, right one manually.
rightIdx = rightIdx - 1
# Store current values and update.
highLeft[leftIdx] = highLeftVal
if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]
lowRight[rightIdx] = lowRightVal
if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]
然后检查每个单元格(第一个和最后一个单元格)以确保该值都大于(根据您的问题,此答案假设"更高/更低"是字面值,而不是"更大/更小"或等于")左边的最高点和右边的最低值:
for each idx 1 thru cell.lastIndex-1 inclusive:
if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]
print "Found value ", cell[idx], " at index ", idx
您可以在下面看到初始传递的结果:
highLeft: - 1 3 3 6 6 7 9 9 10 10
cells : 1 3 2 6 5 7 9 8 10 8 11
lowRight: 2 2 5 5 7 8 8 8 8 11 -
^
对于其上下两个值,对值进行排序(不包括)的唯一候选单元格是7标记的^.
现在请记住,这是一个相对容易理解的解决方案,可以找到满足约束条件的多个项目.鉴于您只需要一个项目,可以获得更好的性能(尽管它仍然是O(n)).
基本思路是从左到右遍历数组,对于每个单元格,检查左侧的所有内容是否较低,右侧的所有内容是否较高.
第一点很容易,因为通过从左到右遍历,您可以记住遇到的最高值.第二点似乎涉及以某种方式展望未来,但有一个技巧可以用来避免这种"时间体操".
我们的想法是保持当前单元格左侧看到的最高值和当前答案的索引(最初设置为哨兵值).
如果当前答案是标记值,则选择满足"大于左边所有内容"的第一个单元作为可能的答案.
并且,只要情况仍然如此,那就是您选择的单元格.但是,只要您在右侧找到小于或等于它的那个,它就不再有效,因此您将其丢弃并再次开始搜索.
此搜索从当前点开始,而不是在开始时,因为:
完成非最终项目的处理后,您的答案将是哨兵或几乎满足约束条件的单元格.
我说"差不多"是因为需要进行最后一次检查以确保最终项目大于它,因为您在遍历过程中没有对该项目执行任何检查.
因此,该野兽的伪代码是这样的:
# Store max on left and start with sentinel.
maxToLeft = cell[0]
answer = -1
for checking = 1 to cell.lastIndex-1 inclusive:
switch on answer:
# Save if currently sentinel and item valid.
case -1:
if cell[checking] > maxToLeft:
answer = checking
# Set back to sentinel if saved answer is now invalid.
otherwise:
if cell[answer] >= cell[checking]:
answer = -1
# Ensure we have updated max on left.
if cell[checking] > maxToLeft:
maxToLeft = cell[checking]
# Final check against last cell.
if answer != -1:
if cell[cell.lastIndex] <= cell[answer]:
answer = -1
由于我的伪代码(严重地)基于Python,因此提供一个更具体的代码实例是一件相当简单的事情.首先,"找到所有可能性"选项:
cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
highLeft = [0] * len(cell)
lowRight = [0] * len(cell)
highLeftVal = cell[0]
lowRightVal = cell[len(cell)-1]
rightIdx = len(cell) - 1
for leftIdx in range(1, len(cell)):
rightIdx = rightIdx - 1
highLeft[leftIdx] = highLeftVal
if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]
lowRight[rightIdx] = lowRightVal
if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]
print(highLeft)
print(cell)
print(lowRight)
for idx in range(1, len(cell) - 1):
if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
print("Found value", cell[idx], "at index", idx)
第二个,更有效的选择,但只能找到一种可能性:
cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
maxToLeft = cell[0]
answer = -1
for checking in range(1, len(cell) - 1):
if answer == -1:
if cell[checking] > maxToLeft:
answer = checking
else:
if cell[answer] >=cell[checking]:
answer = -1
if cell[checking] > maxToLeft:
maxToLeft = cell[checking]
if answer != -1:
if cell[len(cell] - 1] <= cell[answer]:
answer = -1
if answer == -1:
print ("Not found")
else:
print("Found value", cell[answer], "at index", answer);
print(highLeft)
print(cell)
print(lowRight)
for idx in range(1, len(cell) - 1):
if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
print("Found value", cell[idx], "at index", idx)
两者的输出(虽然后一个例子只显示最后一行)基本上显示了伪代码的含义:
[0, 1, 3, 3, 6, 6, 7, 9, 9, 10, 10]
[1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
[2, 2, 5, 5, 7, 8, 8, 8, 8, 11, 0]
Found value 7 at index 5
创建一个通过在源数组上从左到右计算的附加数组.对于此数组中的任何索引N,该值是在第一个数组中0:N-1之间观察到的最高值.
int arr1 = new int[source.length];
int highest = MIN_INT;
for (int i = 0; i < source.length; i++) {
arr1[i] = highest;
if (source[i] > highest) {
highest = source[i];
}
}
现在创建一个第二个数组,通过从右到左扫描形成,其中索引N处的任何值表示在N + 1之间看到的最低值:结束
arr2 = new int[source.length];
int lowest = MAX_INT;
for (int i = (source.length-1); i <= 0; i--) {
arr2[i] = lowest;
if (source[i] < lowest) {
lowest = source[i];
}
}
现在你基本上有三个数组:
source: 1 3 2 6 5 7 9 8 10 8 11
arr1: MIN 1 3 3 6 6 7 9 9 10 10
arr2: 2 2 5 5 7 8 8 8 8 11 MAX
现在,您只想将所有三个数组一起扫描,直到找到满足此条件的索引:
arr1[i] < source[i] < arr2[i]
where:
0 < i < (source.length-1)
码:
for (int i = 1; i < (source.length-1); i++) {
if ((arr1[i] < source[i]) && (source[i] < arr2[i])) {
return i; // or return source[i]
}
}
这是O(N)时间.