सॉर्ट किए गए रोटेटेबल ऐरे

Question

में सबसे छोटी संख्या पाएं I इस प्रश्न में एक साक्षात्कार में आया। समाधान प्राप्त करने में मेरी मदद करें।

प्रश्न है:

आप लिया है घूर्णन योग्य सरणी, मैं। ई। सरणी में तत्व होते हैं जिन्हें क्रमबद्ध किया जाता है और इसे गोलाकार रूप से घुमाया जा सकता है, जैसे कि सरणी में तत्व [5,6,10,19,20,29] हैं, फिर पहली बार सरणी घूर्णन हो जाती है [2 9, 5,6,10,19 , 20] और दूसरी बार यह [20,29,5,6,10,19] बन जाता है और इसी तरह।

तो आपको किसी भी बिंदु पर सरणी में सबसे छोटा तत्व ढूंढना होगा। आपको संख्या समय सरणी घूर्णन के साथ प्रदान नहीं किया जाएगा। बस घूर्णन सरणी तत्वों को दिया और उनमें से सबसे छोटा पता लगाएं। इस मामले में उत्पादन होना चाहिए 5.

Answer 1

विधि 1:

आप O(logN) समय में ऐसा कर सकते हैं।

रोटेशन के बिंदु को खोजने के लिए एक संशोधित बाइनरी खोज का उपयोग करें जो एक सूचकांक i है जैसे
arr[i] > arr[i+1]।

उदाहरण:

[6,7,8,9,1,2,3,4,5] 
    ^
     i 

दो उप-सरणियों
(arr[1], arr[2], .., arr[i]) और
(arr[i+1], arr[i+2], ..., arr[n]) हल कर रहे हैं।

जवाब min(arr[1], arr[i+1])

विधि 2 है:

जब आप विभाजित अनुसार क्रमबद्ध, दो हिस्सों (arr[1],..,arr[mid]) और (arr[mid+1],..,arr[n]), उनमें से एक हमेशा क्रमबद्ध हो जाता है और दूसरे में घुमाया सरणी हमेशा मिनट है। हम सीधे एक संशोधित द्विआधारी खोज का उपयोग कर सकते अवर्गीकृत आधा

// index of first element 
l = 0 

// index of last element. 
h = arr.length - 1 

// always restrict the search to the unsorted 
// sub-array. The min is always there. 
while (arr[l] > arr[h]) { 
     // find mid. 
     mid = (l + h)/2 
     // decide which sub-array to continue with. 
     if (arr[mid] > arr[h]) { 
       l = mid + 1 
     } else { 
       h = mid 
     } 
} 
// answer 
return arr[l] 

Answer 2

ऊपर algorihtm विफल रहता है डेटा तत्व {8,8,8,8,8} या {1,8,8 की तरह दोहराया है में खोजना जारी रखना , 8,8} या {8,1,8,8,8} या {8,8,1,8,8} या {8,8,8,8,1}

// solution pasted below will work all test cases :) 

//break the array in two subarray and search for pattern like a[mid]>a[mid+1] 
// and return the min position 

public static int smallestSearch(int[] array,int start,int end) 
{ 
     if(start==end) 
     return array.length; 

     int mid=(start+end)/2; 

     if(array[mid]>array[mid+1]) 
     return min(mid+1,smallestSearch(array,start,mid),smallestSearch(array,mid+1,end)); 
     else 
     return min(smallestSearch(array,start,mid),smallestSearch(array,mid+1,end)); 
} 

public static int min(int a,int b) 
{ 
    if(a==b) 
    return a; 
    else if(a<b) 
     return a; 
     else 
     return b; 
} 
public static int min(int a,int b,int c) 
{ 
    if(a<c) 
    { 
     if(a<b) 
     { 
      return a; 
     } 
     else 
     { 
      return b; 
     } 
    } 
    else 
    { 
     if(b<c) 
     return b; 
     else 
     return c; 
    } 

} 

Answer 3

मेरा कोड टिप्पणियों के रूप में एल्गोरिदम के साथ नीचे है। दोहराए गए तत्वों के लिए भी काम करता है।

//Find Min in Rotated Sorted Array 
//Example: int array[10] = {7, 8, 9, 10, 11, 12, 3, 4, 5, 6}; 
// Min in the above array is 3 
// Solution: Recursively search (Modified binary search) for the Pivot where is the smallest Element is present 
// Algorithm: 
// 1) Find the Mid of the Array 
// 2) call the recursive function on segment of array in which there is a deviation in the order 
// If (A[low] > A[mid]) array segment in which deviation in the order present is (low, mid) 
// If (A[low] < A[mid]) array segment in which deviation in the order present is (mid + 1, high) 
// Time Complexity: O(logn) 
// Space Complexity: is of the recursive function stack that is being used 

#define MIN(x,y) (x) <= (y) ? (x): (y) 

int MininRotatedSortedArray(int A[], int low, int high) 
{ 
    if(low > high) 
     return -1; 

    if(low == high - 1) 
     return MIN(A[low], A[high]); 

    int mid = low + (high - low)/2; 

    if(A[low] > A[mid]) 
     return MininRotatedSortedArray(A, low, mid); 
    else if(A[low] < A[mid]) 
     return MininRotatedSortedArray(A, mid + 1, high); 
    else 
     return A[mid]; 
} 

Answer 4

यह हे में किया जा सकता (1) समय सबसे अच्छा मामले, हे (एन) समय सबसे खराब स्थिति है, और ओ (एलजी एन) औसतन समय।

एक घूर्णन क्रमबद्ध सरणी के लिए, यदि सरणी में पहला तत्व सरणी में अंतिम तत्व से कम है, तो क्रमबद्ध सरणी घुमाया नहीं जाता है (या 0 स्थिति घुमाया जाता है)। न्यूनतम तत्व केवल पहला तत्व है।

यदि मध्य तत्व अंतिम तत्व से कम है, तो न्यूनतम तत्व [पहले, मध्य] में है।

यदि मध्य तत्व अंतिम तत्व से अधिक है, तो न्यूनतम तत्व [मध्य + 1, अंतिम] में है।

1. पहला तत्व पिछले तत्व से भी बड़ा है, ऐसी स्थिति में कम से कम तत्व में [है पहले:

   तो मध्य तत्व पिछले तत्व के बराबर है, तो दो उप मामलों रहे हैं मध्य + 1];

2. पहला तत्व अंतिम तत्व के बराबर है, जिस स्थिति में यह असंगत है जो सरणी के आधा को अस्वीकार करने के लिए है। रैखिक खोज में कमी। उदाहरण के लिए, [5,5,5,1,5] और [5,1,5,5,5] जैसे सरणी के लिए, केवल पहले, अंतिम और मध्य तत्व की जांच करके असंभव है (क्योंकि वे सभी बराबर हैं) सरणी का आधा हिस्सा न्यूनतम तत्व निहित है।

मैंने इस समस्या को हल करने के लिए सी ++ में निम्न कोड लिखा है, जो सभी मामलों (खाली सरणी, दोहराए गए तत्व) को संभालना चाहिए।

template <typename Iterator> 
Iterator rotated_min(Iterator begin, Iterator end) 
{ 
    while (begin != end) 
    { 
     if (*begin < *(end - 1)) 
     { 
      return begin; 
     } 
     Iterator mid = begin + (end - 1 - begin)/2; 
     if (*mid < *(end - 1)) 
     { 
      end = mid + 1; 
     } 
     else if (*mid > *(end - 1)) 
     { 
      begin = mid + 1; 
     } 
     else 
     { 
      if (*begin > *(end - 1)) 
      { 
       end = mid + 1; 
       ++begin; 
      } 
      else 
      { 
       //reduce to linear search 
       typename ::std::iterator_traits<Iterator>::value_type min_value = *begin; 
       Iterator min_element = begin; 
       for (Iterator i = begin + 1; i != end; ++i) 
       { 
        if (*i < min_value) 
        { 
         min_value = *i; 
         min_element = i; 
        } 
       } 
       return min_element; 
      } 
     } 
    } 
    return begin; 
} 

Answer 5

परिपत्र क्रमबद्ध सरणी में मिन सूचकांक खोजें

Example : [7,8,9,1,2,3,4,5,6] 

int findMinIndex(int []a, int start, int end) 
{ 
    int mid = (start + end)/2; 

    if (start - end == 1) 
     if(a[start] < a[end]) 
     return start; 
     else 
     return end; 

    if (a[mid] > a[end]){ 

    return findMinIndex(a,mid,end); 

    } 

    else{ 

     return findMinIndex(a,start,mid); 
    } 

    return -1; //Not found 
} 

Answer 6

मामले में किसी भी एक की जरूरत है यह .. जावा में मेरे कार्यान्वयन ..

अनुसार क्रमबद्ध/अवर्गीकृत आरोही // अवरोही क्रम का ख्याल रखता है usecases ..

दोष यह है कि यह अभी भी एक घूर्णन के साथ पूरी तरह से क्रमबद्ध सेट में न्यूनतम मान खोजने के लिए लॉग एन चरणों का पालन करेगा।

http://ideone.com/fork/G3zMIb

/* package whatever; // don't place package name! */ 

import java.util.*; 
import java.lang.*; 
import java.io.*; 

/* Name of the class has to be "Main" only if the class is public. */ 
class Ideone 
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     int [] a = {3,3,0,2,2,2,2,1,2,2,2,2,2,2,2,2,2}; 
     System.out.println(recursiveSplit(a,0,a.length-1)); 
    } 

    public static int findMin(int x, int y){ 
     if(x<=y){ 
      return x; 
     }else{ 
      return y; 
     } 
    } 

    public static int recursiveSplit(int[] arr , int a , int b){ 
     int mid = (int) Math.floor(a + (b-a)/2); 
     int h1_l = a; 
     int h1_u = mid; 
     int h2_l = mid+1; 
     int h2_u = b; 
     int x=0; 
     int y=0; 

     //single element 
     if(a==b){ 
      return arr[a]; 
     } 

     //adjacent positions 
     if(h1_u-h1_l==1){ 
      x=findMin(arr[h1_u],arr[h1_l]); 
     }else{ 
      //else split 
      x=recursiveSplit(arr,h1_l,h1_u); 
     } 

     if(h2_u-h2_l==1){ 
      y=findMin(arr[h2_u],arr[h2_l]); 
     }else{ 
      y=recursiveSplit(arr, h2_l,h2_u); 
     } 

     return findMin(x, y); 
    } 
} 

त्रुटियाँ/सुझाव/विफल रही usecases स्वागत कर रहे हैं

Answer 7

public int findMin(int[] num) { 
     return findMin(num, 0, num.length-1); 
    } 
    public int findMin(int[] num, int left, int right){ 
     if(left==right) return num[left]; 
     if(left+1==right) return Math.min(num[left], num[right]); 
     int mid = (left+right)/2; 
     if(num[mid]>num[right]){ 
      return findMin(num,mid+1,right); 
     }else if(num[mid]<num[right]){ 
      return findMin(num,left,mid); 
     }else{ 
      if(num[mid]==num[left]){ 
       return Math.min(findMin(num,left,mid), findMin(num,mid,right)); 
      }else{ 
       return findMin(num,left,mid); 
      } 
     } 
    } 

Answer 8

निम्नलिखित कलन विधि लॉग (एन) समय लगता है। मान लें कि सरणी में कोई डुप्लिकेट नहीं है।

public int findMin(int[] num) { 
    if(num.length == 0) return -1 
    int r = num.length-1, l = 0; 
    while(l<r){ 
     if(num[l]<=num[r]) return num[l]; //when not rotated, return the left most value 
     int mid = (r+l)/2; 
     if(num[mid]<num[r]){ 
      r = mid; 
     }else{ 
      l = mid+1; 
     } 
    } 
    return num[l]; 
} 

Answer 9

मैंने इसे बाइनरी खोज के थोड़ा संशोधित संस्करण का उपयोग करके किया। मैं यहां क्या कर रहा हूं कि मैं कहां से कम हो सकता है, इस आधार पर मैं बाएं या दाएं जा रहा हूं। उदाहरण के लिए आरोही सरणी में यदि मध्य तत्व बाएं अधिकांश तत्व से कम है, तो यह संभव है कि न्यूनतम बाईं ओर हो। सरणी के माध्यम से रिकर्स करते समय, मैं न्यूनतम का ट्रैक भी रखता हूं। पुनरावृत्ति अंत तक जारी है और फिर नवीनतम मिनट वापस आ गया है। यह दोहराए गए तत्वों के साथ भी काम करता है।

public static void main(String[] args) throws IOException { 

    int[] rotated = {6, 7, 8, 1, 2, 3, 4, 5}; 
    int min = findMin(rotated); 
    System.out.println(min);//1 


} 

public static int findMin(int[] sorted) { 
    return findMinRecursively(sorted, sorted[0], 0, (sorted.length - 1)); 
} 


private static int findMinRecursively(int[] sorted, int min, int leftIndex, int rightIndex) { 

    if (leftIndex > rightIndex) { 
     return min; 
    } 

    int midIndex = (leftIndex + rightIndex)/2; 
    if (sorted[midIndex] < min) { 
     min = sorted[midIndex]; 
    } 

    if (sorted[midIndex] < sorted[leftIndex]) { 
     return findMinRecursively(sorted, min, leftIndex, (midIndex - 1)); 
    } else { 
     return findMinRecursively(sorted, min, (midIndex + 1), rightIndex); 
    } 
}