Geek asks and answers

Definition of the divide and conquer algorithm

Now that I have N different intergers, I need to find the interval that has the largest number whose value is between the endpoints of the O (NlogN) time interval. I call this the divide and conquer problem because it is in my final divide and win exam. I thought about this for 2 weeks and did a lot of experiments, none of them are correct (compared to brute force algorithm). Can someone help me?

examples:

8,1,3,4,7. The answer is 1-7.

2,6,5,4,9,8. The answer is 2-9 or 2-8.

I think the word "interval" does not express my meaning. I want to find the subsequence of the array with the largest number whose value is between the endpoints of the subsequence. For example: “1,3,4,7” has two numbers (3,4) and, for example, 2: both “2,6,5,4,9” and “2,6,5,4,9, 8 "have three numbers (6,5,4).

here is my code (O (n ^ 2)). @Vaughn Cato I use this to compare with your code.

#! /usr/bin/env python
#coding=utf-8
import itertools
def n2(numbers):
  a = [0]*len(numbers)
  ans = -1
  l = 0
  r = 0
  for j in range(1,len(numbers)):
    t = 0
      for i in range(j-1,-1,-1):
        if numbers[i]<numbers[j]:
          x = t - a[i]
          if x>ans:
            ans = x
            l = i
            r = j
          t += 1
        else:
          a[i] += 1
  return (numbers[l],numbers[r],ans)

def countBetween(numbers,left,right):
  cnt = 0
  for i in range(left+1,right):
    if numbers[left]<numbers[i]<numbers[right]:
      cnt += 1
  return cnt

for numbers in itertools.permutations(range(5)):
  ans1=n2(numbers)
  ans2=longestInterval(numbers)
if(ans1[2]!=ans2[2]):
  print ans1,ans2,numbers
+5
source share
2 answers

NOTE. This does not actually work, but may give you some ideas.

Think of it this way:

  • Let be Xan array of numbers.
  • Let be the sindex of the beginning of the subsequence.
  • Let be the eindex of the end of the subsequence.

p, , . , s < p <= e. s, s p, X [s]. "e", p e, X [e].

, , .

, , , , X, :

, , . , , , , , ( , ). , . .

, .

- , . , , .

python:

# Find the index from the given indices that has the most numbers to the
# right of it which are greater in value.  The indices are sorted by
# the value of the numbers at that index. We don't even need to know
# what the numbers are.
def longestLowerSequence(indices):
  best_index=indices[0]
  target_index=best_index
  for i in range(0,len(indices)):
    if indices[i]<target_index:
      best_index=indices[i]
      target_index=best_index
    else:
      target_index-=1
  return best_index

# Find the index from the given indices that has the most numbers to the
# left of it which are less in value.
def longestUpperSequence(indices):
  n=len(indices)
  best_index=indices[n-1]
  target_index=best_index
  for i in range(0,n):
    if indices[n-1-i]>target_index:
      best_index=indices[n-1-i]
      target_index=best_index
    else:
      target_index+=1
  return best_index

# Return the pair of indices which has the most values between it.
def longestRangeFromSortedIndices(numbers,indices,begin,end):
  assert end>begin
  if end-begin<=2:
    return (indices[begin],indices[end-1])
  assert type(indices) is list
  partition=(begin+end)/2
  left_indices=filter(lambda index: index<partition,indices)
  right_indices=filter(lambda index: index>=partition,indices)
  assert len(left_indices)>0
  assert len(right_indices)>0
  left=longestLowerSequence(left_indices)
  right=longestUpperSequence(right_indices)
  left_range=longestRangeFromSortedIndices(numbers,indices,begin,partition)
  right_range=longestRangeFromSortedIndices(numbers,indices,partition,end)
  best_size=countBetween(numbers,left,right)
  best_range=(left,right)
  left_size=countBetween(numbers,left_range[0],left_range[1])
  right_size=countBetween(numbers,right_range[0],right_range[1])
  if left_size>best_size:
    best_size=left_size
    best_range=left_range
  if right_size>best_size:
    best_size=right_size
    best_range=right_range
  return best_range

def sortedIndices(numbers):
  return sorted(range(len(numbers)),key=lambda i: numbers[i])

def longestInterval(numbers):
  indices=sortedIndices(numbers)
  longest_range=longestRangeFromSortedIndices(numbers,indices,0,len(numbers))
  return (numbers[longest_range[0]],numbers[longest_range[1]])
+1

, .

, divide :

  • R1, R2 (R1, R2 - , )

  • MIN MAX R3 MIN MAX (MIN MAX )

  • R1, R2 R3

:

: 1) 2) 3) . , .

:

:

T(n) = 2T(n/2) + O(n)

T(n) = O(nlogn). : (2T(n/2)) (O(n)).

0

More articles:


All Articles