Matrice ordinata ma ruotata

Question

Dato un array ordinato ma ruotato, come si trova il pivot? Mi è stata fatta questa domanda in un'intervista. Cos'è un array ruotato?

Ho trovato questo su internet ma non è affatto chiaro.

In una matrice di ordinamento ruotata, è possibile garantire che solo una tra A e B sia ordinata.

Pivot è l'elemento che è minore anche nell'elemento sinistro e nell'elemento destro.

Answer 1

Penso che un ordinato, un array ruotato è qualcosa di simile:

Ordinati:

2, 7, 32, 48, 55 

ruotato:

32, 48, 55, 2, 7 

2 è il perno. Devi trovare la posizione del perno.

La soluzione deve essere semplice: il pivot è il punto in cui termina l'ordinamento e ricomincia. Questo è anche ciò che si "trovato su Internet":

(array assumendo è ordinato in ordine crescente Se l'ordine decrescente, cambiare <->.)

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

Aggiunto: Un divide et impera la logica che potrei rapidamente pensare. Continua a dividere l'array finché il primo elemento è più grande dell'ultimo elemento. Se il primo elemento dell'array split (sub) non è più grande dell'ultimo elemento, il primo è il pivot dell'array originale.

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; 

A proposito, se v'è stato chiesto a questa domanda in un'intervista, e non sapevi cosa una matrice ruotata ordinato è, si può chiedere. Se l'intervistatore te lo spiega e poi dai loro una soluzione, dovresti essere bravo. Personalmente non mi interessa se qualcuno non conosce la terminologia. Finché possono pensare, trovare logica e codice, dovrebbe andare bene.

Answer 2

Ho implementato l'algoritmo D & D @Nivas descritto, con casi limite gestiti, in Java. Vedi sotto codice e test.

Codice:

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; 
    } 
} 

prova:

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); 
    } 
}