foo
BAN USERunemployed se
python:
def exch(i,j,sentence):
c = sentence[i]
sentence[i] = sentence[j]
sentence[j] = c
def revWord(start,end,sentence):
while end > start:
exch(start,end,sentence)
end -= 1
start += 1
def revWords(sentence):
start = 0
end = len(sentence)
for i in range(0,end):
c = sentence[i]
if (c == ' ') or (i == (end-1)):
e = i-1 if c == ' ' else i
revWord(start,e,sentence)
start = i+1
here's a solution in python
def divide(na,lo,hi):
last = na[hi]
next2last = na[hi-1]
if last > next2last:
# we are still increasing,
#so, no sense digging into this half of the array
return last
if lo >= hi: #pointers crossed
return last
mid = lo + (hi - lo ) / 2
leftone = divide(na,lo,mid)#look at left half
rightone = divide(na,mid+1,hi)#look at right half
return leftone if leftone > rightone else rightone
#na is an array of numbers that increase and then decrease
#objective is to find the maximum
def convexSearch(na):
lo = 0
hi = len(na) - 1
winner = divide(na,0,hi)
print "highest is: " , winner·
The problem statement says the array is already sorted, so you don't need to bother with all this decrementing counter stuff. Just count instances of last letter, if the counter exceeds max, update max and max letter. O(n)
- foo May 08, 2014