查找已排序的循環整數數組的起點索引

將兩個排序的連續數組數組合併到一個數組中。這兩個陣列都有不同的數字。查找已排序的循環整數數組的起點索引

ex : 
{1, 2, 3, 4, 5, 6, 7, 8, 9} and 
{10, 11, 12, 13, 14} 

int[] resultArr = {10, 11, 12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 
            ^

查找起點索引的算法。如果我們把它當作循環數組，它將在從起始點迭代的同時按排序順序排列。

在上面的例子中的起始索引會「4」

我已經寫了下面的示例程序來解決這個問題，但對時間複雜度不開心。

有人可以告訴我下面的代碼的時間複雜性，並提供一個更好的解決方案，這個問題。

public class FindStartingPoint { 

    public static Integer no = null; 

    private static void findStartingPoint(int[] arr, int low, int mid, int high) { 
    if (no != null) 
     return; 
    else if (high - low <= 1) 
     return; 
    else if (arr[mid] > arr[mid + 1]) { 
     no = mid + 1; 
     return; 
    } 
    findStartingPoint(arr, low, (low + mid)/2, mid); 
    findStartingPoint(arr, mid, (mid + high)/2, high); 
    } 

    public static void main(String[] args) { 
    int[] arr = {12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; 
    findStartingPoint(arr, 0, arr.length/2, arr.length - 1); 
    System.out.println(no); 
    } 
}

在此先感謝。 :-)

來源

2015-11-16 Ashis Jena

等等，你是否試圖找到數組中的最低數字？ – basic

@JordanSeanor，不，我試圖找出最低數組的索引（這將是起點） –

如果兩個數組是'{1,2,3}'和'{4,5， 6}'，沒有解決方案，因此僅僅進行排序並且具有不同的元素是不夠的。 – biziclop

二進制搜索也適合這裏。對數。

public int findStart(int[] numbers) { 
    int low = 0; 
    int high = numbers.length; // Exclusive 
    while (low < high) { 
     int middle = (low + high)/2; 
     boolean fitsLow = numbers[low] <= numbers[middle]; 
     if (fitsLow) { 
      low = middle + 1; 
     } else { 
      high = middle; 
     } 
    } 
    return low; 
}

來源

2015-11-16 14:04:17

@biziclop - 使用Dijkstra的'[低，高]'約定 –

是的，在評論後馬上意識到它。 :) – biziclop

還值得評論。 ;） –

它是不是從你的描述完全清楚，但如果所有的號碼數量最少的右邊是比他們都向左側越小，分而治之的算法是這樣的：

從第一個元素的左邊界開始，最後一個右邊界開始。
取左邊界和右邊界中間的元素。
如果中間元素大於左邊界，則將左邊界移到中間元素。
如果中間元素小於左邊界，則將右邊界移到中間元素。
從2開始重複，直到你的範圍內只有1個元素。

來源

2015-11-16 14:04:55 biziclop

您可以優化一點。你有這個代碼...

findStartingPoint(arr, low, (low + mid)/2, mid); 
findStartingPoint(arr, mid, (mid + high)/2, high);

你實際上只需要調用其中一個不是兩個。

例如，如果mid的編號小於low的編號，那麼您需要長時間撥打第一個編號，因爲編號必須位於mid的左側。否則，你只需要撥打第二個電話。

這會加快速度。

如果這是面試，那麼我建議您在代碼運行時重構代碼，使其不那麼有狀態。我假設你現在只是在玩弄目前的工作。

來源

2015-11-16 14:16:14

查找已排序的循環整數數組的起點索引

回答

相關問題