给定一个排序但旋转的数组，你如何找到枢轴？我在一次采访中被问到这个问题。什么是旋转数组？
我在互联网上得到了这个，但根本不清楚。
在一个旋转排序的数组中，只能保证 A 和 B 中的一个被排序。
枢轴是比左元素和右元素更小的元素。
问问题
8914 次
2 回答
16
我认为一个排序的、旋转的数组是这样的：
排序：
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;
顺便说一句，如果你在面试中被问到这个问题，并且你不知道什么是排序旋转数组，你可以问。如果面试官向你解释，然后你给他们一个解决方案，你应该很好。就我个人而言，我不在乎有人不知道术语。只要他们能思考，能找到逻辑和代码，应该没问题。
于 2012-10-18T19:47:08.537 回答
2
我用 Java 实现了 @Nivas 描述的 D&D 算法，并处理了边缘情况。请参阅下面的代码和测试。
代码：
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);
}
}
于 2015-10-23T10:16:22.953 回答