algorithm - 在具有重复元素的排序和旋转数组中查找最小数

Question

我已经处理这个问题好几天了，但仍然找不到解决它的方法。我的解决方案无法解决某些边缘情况。
问题:
给定一个按升序排列的数组，将数组旋转k个元素，找到数组中最小个数的索引(原未旋转数组的第一个元素)。例如:
1. 给出 {3,4,1,3,3}，返回 2。
2. 给出{3,3,3,3,3}，返回0。
3. 给出 {1,1,4,1,1,1}，返回 3。
没有重复项，这个问题可以使用二分查找在 O(logn) 时间内解决，有重复项可以使用修改后的二分查找，最坏情况下时间复杂度为 O(n)。
我的代码:

public int FindPivot(int[] array)
{
    var i = 0;
    var j = array.Length - 1;
    while (i < j)
    {
        var mid = i + (j - i) / 2 + 1;
        if (array[mid] < array[array.Length - 1])
        {
            j = mid - 1;
        }
        else if (array[mid] > array[array.Length - 1])
        {
            i = mid;
        }
        else
        {
            if (array[mid] == array[j])
            {
                j--;
            }
            if (array[mid] == array[i])
            {
                i++;
            }
        }
    }
    return i+1;
}

如果输入为{3,3,1,3,3,3,3,3}则无效，返回3而正确答案为2。因为最后一步是i指向index 2 和 j 从索引 3 移动到索引 2，它得到了正确的元素，但 i+1 使结果错误。我在这里错过了什么？

Answer 1

我已按如下方式修改了您的代码，它似乎适用于所有情况。

我想不出任何处理所有极端情况的好方法，因为您的原始代码混合了没有重复元素的算法(分为两个子数组)和存在重复元素时的双指针算法的概念.

我会说问题是 else移动两个指针的情况并未涵盖所有情况，就像您有可能进入 else用 array[i] < array[mid] block

---

因此我只是使用新手的方法对其进行了修改:添加两个变量来跟踪我们找到的最小元素和最小索引。每当指针移动以涵盖所有可能的情况时更新它。最后返回索引。你不能做像 return i+1 这样的事情因为它不会处理 k = 0 的情况根本没有旋转({1,2,3,4})

修改后的代码是用 C# 编写的，我从您的示例代码中猜测。

---

PS: 虽然平均而言，这比 O(N) 快如果数据是部分排序的，没有重复元素，最坏的情况仍然是 O(N)正如你提到的。所以如果我是你，我会做一个简单的迭代并找到第一个最小元素......

也来自这个reference , O(N)如果有重复元素，您可以达到最佳效果。

---

http://ideone.com/v3KVwu

using System;

public class Test
{
    public static int FindPivot(int[] array)
    {
        var i = 0;
        var j = array.Length - 1;
        var ans = 1<<20;
        var idx = 1<<20;

        while (i < j)
        {
            var mid = i + (j - i) / 2 + 1;
          //  Console.WriteLine(String.Format("{0}, {1}, {2}", i, mid, j));

            if (array[mid] < array[array.Length - 1])
            {
                if(array[mid] < ans || (array[mid] == ans && mid < idx)) { ans = array[mid];  idx = mid;}
                j = mid - 1;
            }
            else if (array[mid] > array[array.Length - 1])
            {
                i = mid;
            }
            else
            {

                // Here did not consider case if array[i] < mid  
                if(array[j] < ans || (array[j] == ans && j < idx)) { ans = array[j];  idx = j;}
                if(array[i] < ans || (array[i] == ans && i < idx)) { ans = array[i];  idx = i;}
                if (array[mid] == array[j])
                {
                    j--;
                }
                if (array[mid] == array[i])
                {
                    i++;
                }
            }
        }
        if(array[j] < ans || (array[j] == ans && j < idx)) { ans = array[j];  idx = j;}
        if(array[i] < ans || (array[i] == ans && i < idx)) { ans = array[i];  idx = i;}
        Console.WriteLine("Minimum = " + ans);
        return idx;
    }

    public static void Main()
    {
        int []a = {7,7,7,7,8,8,9,9,1,2,2,2,7,7};
        int []b = {3,3,1,3,3,3,3,3};
        int []c = {1,2,3,4};
        int []d = {4,4,4,4};
        int []e = {3,3,3,3,3,3,3,1,3};
        int []f = {4,5,6,7,1,1,1,1};
        Console.WriteLine(FindPivot(a));
        Console.WriteLine(FindPivot(b));
        Console.WriteLine(FindPivot(c));
        Console.WriteLine(FindPivot(d));
        Console.WriteLine(FindPivot(e));
        Console.WriteLine(FindPivot(f));
    }
}