This problem can be simply seen as a searching problem in a sorted array. The only difference is to first find the start and end point and extend the index. The extended virtual index will not cause extra space, because you do not need to store them at the end of the original array, but only map them to the original ones. As shown below:
class Solution: # @param A a list of integers # @param target an integer # @return a boolean def search(self, A, target): if len(A) == 0: return False else: start = 0 end = len(A) - 1 # To find the start point(smallest integer) for i in range(len(A)-1): if A[i] > A[i+1]: start = i+1 end = i + len(A) # Extend the index of the list while start<=end: mid = start + (end - start)/2 cur = A[mid%len(A)] #To get the index in original list if cur == target: return True elif cur > target: end = mid - 1 else: start = mid + 1 return False
Nice idea. One advice, you can always use 'cur = A[mid%len(A)]' to get original index.
I thinks the key problem is to find the starting point and the worst case should take O(n) time(like case (a,a,a,a,a,a,a,a,a,a,a,a,b,a,a), b. But if use O(n), just use one loop to find A[i] == target is OK.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.