सॉर्ट किया गया लेकिन घुमावदार सरणी

Question

एक सॉर्ट किए गए लेकिन घूर्णन सरणी को देखते हुए आपको पिवट कैसे मिलती है? मुझे एक साक्षात्कार में इस सवाल से पूछा गया था। घूर्णन सरणी क्या है?

मुझे यह इंटरनेट पर मिला लेकिन यह बिल्कुल स्पष्ट नहीं है।

एक घूर्णन क्रमबद्ध सरणी में, केवल ए और बी में से एक को सॉर्ट करने की गारंटी दी जा सकती है।

पिवोट वह तत्व है जो बाएं तत्व और दाहिने तत्व में भी कम है।

Answer 1

मुझे लगता है कि एक हल कर, घुमाया सरणी कुछ इस तरह है:

छाँटे गए:

2, 7, 32, 48, 55 

घुमाया गया:

32, 48, 55, 2, 7 

2 धुरी है। आपको पिवट की स्थिति खोजने की जरूरत है।

समाधान सरल होना चाहिए: पिवट वह बिंदु है जहां सॉर्टिंग समाप्त होती है और फिर से शुरू होती है। यह भी है कि तुम क्या "इंटरनेट पर पाया":

(यह मानते हुए सरणी आरोही क्रम में सॉर्ट किया जाता है तो अवरोही क्रम, <> लिए बदल जाते हैं।)

for (i = 0; i<array.length; i++) 
{ 
    if array[i+1] < array[i] 
     return i + 1; 
     break; 
} 

जोड़ा गया: एक फूट डालो और जीत के तर्क कि मैं जल्दी से सोच सकता था। सरणी को तब तक विभाजित रखें जब तक कि पहला तत्व अंतिम तत्व से बड़ा न हो। यदि विभाजन (उप) सरणी का पहला तत्व अंतिम तत्व से बड़ा नहीं है, तो पहला मूल सरणी का मुख्य भाग है।

int left = 0; 
int right = array.length - 1; 
while (array[left] > array[right]) 
{ 
    int mid = left + (left + right)/2; 
    if(array[mid] > array[right]) 
    { 
     left = mid + 1; 
    } 
    else 
    { 
     right = mid; 
    } 
} 
return left; 

Btw, यदि आप एक साक्षात्कार में यह सवाल पूछा गया, और आप पता नहीं था क्या एक हल कर घुमाया सरणी है, तो आप पूछ सकते हैं। यदि साक्षात्कारकर्ता आपको यह समझाता है और फिर आप उन्हें समाधान देते हैं, तो आपको अच्छा होना चाहिए। व्यक्तिगत रूप से मुझे कोई परवाह नहीं है अगर कोई शब्दावली नहीं जानता है। जब तक वे सोच सकते हैं, तर्क और कोड पाएं, यह ठीक होना चाहिए।

Answer 2

मैंने डी & डी एल्गोरिदम @ निवास को वर्णित किया, जावा में किनारे के मामलों को संभाला गया। कोड और परीक्षण नीचे देखें।

कोड:

import org.apache.log4j.Logger; 

import java.util.Collections; 
import java.util.List; 
import java.util.Random; 

public class RotatedListFindPivot { 
    private static final Logger logger = Logger.getLogger(RotatedListFindPivot.class); 

    /** 
    * With a sorted then rotated list, return the pivot (i.e. smallest or largest), 
    * depending on if it was ASCENDING or DESCENDING 
    * <p> 
    * Multiple appearance of the same value is allowed. It will work as defined: 
    * return the smallest/largest, or one of the smallest/largest elements 
    * <p> 
    * In the extreme case where all elements in the list are equal, it returns any element 
    * 
    * @param list 
    * @param sortingOrder 
    * @param <E> 
    * @return the pivot 
    */ 

    public static <E extends Comparable> E rotatedListFindPivot(List<E> list, Util.SortingOrder sortingOrder) { 
     if (list == null || list.size() == 0) { 
      return null; 
     } 
     if (list.size() == 1) { 
      return list.get(0); 
     } 
     /* 
     Divide and Conquer. Given a rotated list, pick any element to be mid (the first of right half), 
     It holds that only either one half is sorted. If both halves sorted, then left most element is pivot 
     */ 
     int left = 0, right = list.size() - 1; 
     /* 
     First need to deal with special case: 3,3,3,1,2,3,3,3,3,3,3 
     This will seem as if both halves sorted. 
     */ 

     E removedFlatEdge = null; 
     if (list.get(left).equals(list.get(right))) { 
      removedFlatEdge = list.get(0); 
     } 
     while (right > left 
       && list.get(left).equals(list.get(right)) 
       && list.get(left).equals(removedFlatEdge)) { 
      right--; 
      left++; 
     } 
     if (right < left) { 
      return removedFlatEdge; 
     } 
     E result = rotatedListFindPivotRecur(list, left, right, sortingOrder); 
     return removedFlatEdge == null ? result : (removedFlatEdge.compareTo(result) < 0 ? removedFlatEdge : result); 
    } 

    private static <E extends Comparable> E rotatedListFindPivotRecur(List<E> list, int left, int right, Util.SortingOrder sortingOrder) { 
     if (left == right) { 
      return list.get(left); 
     } 

     int mid = left + (int) Math.ceil(((double) right - left)/2); 

     /* 
     Both sorted. Is there a rotation (gap)? 
     */ 
     if (list.get(left).compareTo(list.get(mid - 1)) <= 0 && list.get(mid).compareTo(list.get(right)) <= 0) { 
      if (list.get(mid - 1).compareTo(list.get(mid)) <= 0) { 
       /* 
       No gap 
       */ 
       return list.get(left); 
      } else { 
       /* 
       There is a gap. Mid is pivot 
       */ 
       return list.get(mid); 
      } 

     } 

     /* 
     Left half sorted 
     */ 
     if (list.get(left).compareTo(list.get(mid)) <= 0) { 
      return rotatedListFindPivotRecur(list, mid + 1, right, sortingOrder); 
     } 

     /* 
     Right half sorted 
     */ 
     if (list.get(mid).compareTo(list.get(right)) <= 0) { 
      return rotatedListFindPivotRecur(list, left, mid - 1, sortingOrder); 
     } 

     logger.warn("Should never reach here"); 
     return null; 
    } 

    public static <E extends Comparable> E rotatedListFindPivotNaive(List<E> list, Util.SortingOrder sortingOrder) { 
     if (list == null || list.size() == 0) { 
      return null; 
     } 

     boolean isAscending = sortingOrder == Util.SortingOrder.ASCENDING ? true : false; 
     E pivot = list.get(0); 
     for (E e : list) { 
      if ((e.compareTo(pivot) < 0) == isAscending) { 
       pivot = e; 
      } 
     } 

     return pivot; 
    } 

    public static <E> List<E> rotate(List<E> input) { 
     Random random = new Random(); 
     int rotateBy = random.nextInt(input.size()); 
     Collections.rotate(input, rotateBy); 
     return input; 
    } 
} 

टेस्ट:

import org.junit.Test; 

import java.util.*; 

import static org.junit.Assert.assertEquals; 

public class RotatedListFindPivotTest { 

    private static final int RANDOM_LIST_LOW = 1; 
    private static final int RANDOM_LIST_SIZE = 12; 
    private static final int RANDOM_LIST_HIGH = 6; 
    private static final int NUM_RANDOM_TESTS = 12000000; 

    @Test 
    public void testTwoLevelsOfPlateaus() throws Exception { 

     Integer result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("TwoLevelsOfPlateaus: [3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3]", new Integer(1), result); 
    } 

    @Test 
    public void testRotatedListFindPivotRemovedEdgeIsPivot() throws Exception { 
     Integer result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(0, 0, 2, 3, 3, 3, 4, 4, 5, 5, 0, 0)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("RemovedEdgeIsPivot: [0, 0, 2, 3, 3, 3, 4, 4, 5, 5, 0, 0]", new Integer(0), result); 
    } 

    @Test 
    public void testRotatedListFindPivotRandomized() throws Exception { 

     for (int i=0; i<NUM_RANDOM_TESTS; i++) { 
      List<Integer> input = Util.getRandomIntegerList(RANDOM_LIST_SIZE, RANDOM_LIST_LOW, RANDOM_LIST_HIGH); 
      Collections.sort(input); 
      input = RotatedListFindPivot.rotate(input); 
      Integer naiveResult = RotatedListFindPivot.rotatedListFindPivotNaive(input, Util.SortingOrder.ASCENDING); 
      Integer result = RotatedListFindPivot.rotatedListFindPivot(input, Util.SortingOrder.ASCENDING); 
      assertEquals("Results must hold for inputs: " + input, naiveResult, result); 
     } 

    } 

    @Test 
    public void testRotatedListFindPivotTwoSegmentFlatList() throws Exception { 
     Integer result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(3, 3, 1, 1)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Two Segment flat list should return any from right half, {3,3,1,1}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(3, 3, 3, 1, 1)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Two Segment flat list should return any from right half, {3,3,3,1,1}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(3, 3, 1, 1, 1)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Two Segment flat list should return any from right half, {3,3,1,1,1}", new Integer(1), result); 
    } 

    @Test 
    public void testRotatedListFindPivotSingletonList() throws Exception { 
     Integer result = RotatedListFindPivot.rotatedListFindPivot(
       Collections.singletonList(1), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Singleton list should return the elem, {1}", new Integer(1), result); 
    } 

    @Test 
    public void testRotatedListFindPivotSimpleFlatList() throws Exception { 
     Integer result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(1, 1)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Total flat list should return any elem, {1,1,1}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(1, 1, 1)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Total flat list should return any elem, {1,1,1}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(1, 1, 1, 1)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Total flat list should return any elem, {1,1,1,1}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(2, 1, 2, 2)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Simple flat list should work, {2,1,2,2}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(2, 2, 1, 2)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Simple flat list should work, {2,2,1,2}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(2, 1, 2)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Simple flat list should work, {2,1,2}", new Integer(1), result); 
    } 

    @Test 
    public void testRotatedListFindPivotEmptyList() throws Exception { 
     Integer result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Empty list should return null", null, result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       null, 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Null list should return null", null, result); 
    } 

    @Test 
    public void testRotatedListFindPivotSimpleCase() throws Exception { 
     Integer result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(1, 2, 3)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Not rotated should return pivot, {1,2,3,4}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(4,1,2,3)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Simple case should hold, {4,1,2,3}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(4,1,2,3)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Simple case should hold, {3,4,1,2}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(4,1,2,3)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Simple case should hold, {3,4,1,2}", new Integer(1), result); 

     result = RotatedListFindPivot.rotatedListFindPivot(
       new ArrayList<Integer>(Arrays.asList(4,1,2,3)), 
       Util.SortingOrder.ASCENDING); 
     assertEquals("Simple case should hold, {2,3,4,1}", new Integer(1), result); 
    } 
}