如何找到排序一个数组所需的最大组数？

Question

假设我有一个数组：

[1, 8, 5, 6, 10, 9, 11, 12];

我希望按升序对其进行排序，但是找出我需要排序的最大组数。在这个例子中，答案是：

[1], [8,5,6], [10,9], [11], [12]: so 5

[3, 2, 1]将变成1，因为整个数组需要排序。

我完全不知道如何做到这一点，希望能得到正确的方向提示。

- phevin

---

你可以遍历数组并计算n[i+1] > n[i]的次数。 - GrumpyWelshGit

看起来这是一个适用于Tarjan强连通分量算法的好案例。 - Andrey Tyukin

@GrumpyWelshGit 这不起作用，因为一个更大的数字可能在一组中间。 - phevin

如果你加上2，结果将是[1,8,5,6,10,9,2]，[11]，[12] = 3？ - Dimitar Spasovski

@Dvorog，它将是[1]，[8,5,6,10,9,2]，[11]，[12] = 4。 1已处于正确的位置，因此它是自己的组，与11和12相同。 - phevin

Answer 1

我的解决方案使用插入排序算法，该算法将已排序的元素保持在其位置，将未排序的元素向数组的开头移动，直到它们到达其位置。我们可以利用这种行为来检测需要排序的组。

在每次迭代中，我们检查当前元素是否大于或等于前一个元素。如果是，则可能遇到了新组。我们将当前索引推送到堆栈中。

如果当前元素小于前一个元素，则仍处于同一组中。我们开始交换此元素与先前元素，直到它到位。在每个步骤中，我们检查是否已经越过了先前组的边界。如果越过了边界，则意味着这两个组实际上是一个组，因此我们从堆栈中弹出最后一个值。

最后，组数等于堆栈大小。

以下是实现方式：

public static int countGroups(int[] a) {
    if (a.length < 2) return a.length;
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    for (int i = 1; i < a.length; i++) {
        if (a[i] >= a[i - 1]) stack.push(i);
        for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
            swap(a, j, j - 1);
            if (j <= stack.peek()) stack.pop();
        }
    }
    return stack.size();
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

以下是一段JavaScript代码片段，包含了一些示例：

console.log(countGroups([1, 8, 5, 6, 10, 9, 11, 12]));    //5 - [1], [8, 5, 6], [10, 9], [11], [12]
console.log(countGroups([1, 8, 5, 6, 10, 9, 2, 11, 12])); //4 - [1], [8, 5, 6, 10, 9, 2], [11], [12]
console.log(countGroups([3, 8, 5, 6, 10, 9, 2, 11, 1]));  //1 - [3, 8, 5, 6, 10, 9, 2, 11, 1]
console.log(countGroups([1, 2, 8, 6, 10, 9, 11]));        //5 - [1], [2], [8, 6], [10, 9], [11]
console.log(countGroups([1, 2, 1, 1, 10, 9, 10]));        //4 - [1], [2, 1, 1], [10, 9], [10]

function countGroups(a) {
    if (a.length < 2) return a.length;
    let stack = [0];
    for (let i = 1; i < a.length; i++) {
        if (a[i] >= a[i - 1]) stack.push(i);
        for (let j = i; j > 0 && a[j] < a[j - 1]; j--) {
            swap(a, j, j - 1);
            if (j <= stack[stack.length - 1]) stack.pop();
        }
    }
    return stack.length;
}

function swap(a, i, j) {
   let t = a[i];
   a[i] = a[j];
   a[j] = t;
}

更新：如果您不需要实际对数组进行排序，则似乎可以在线性时间内解决该问题：

public static int countGroupsLinear(int[] a) {
    Stack<Integer> stack = new Stack<>();
    stack.push(a[0]);
    for (int i = 1; i < a.length; i++) {
        if (a[i] >= stack.peek()) stack.push(a[i]);
        else {
            int last = stack.pop();
            while (stack.size() > 0 && a[i] < stack.peek()) stack.pop();
            stack.push(last);
        }
    }
    return stack.size();
}

- Kirill Simonov

---

栈解决方案不是线性时间，如果数组是反向排序的，则在最坏情况下它是二次的。 - thebenman

@thebenman，你的说法是不正确的；栈解决方案是线性时间，因为每个数字只被推入栈一次并且最多弹出一次。 - גלעד ברקן

你说得对。我第一次并没有注意到它，看起来很像插入排序。这也是一个非常巧妙的解决方案。 - thebenman

Answer 2

这是一段适用于n个不同整数数组的C代码。

#include <stdio.h>
//code for the case where each element of the array is distinct 
//and greater than 0
//finding index of the maximum value in array
int maximum(int *a,int n)
{
    int i,max;
    max=0;
    for(i=0;i<n;i++)
    {
        if(a[i]>a[max])
        {
            max=i;
        }
    }
    return max;
}

//finding index of the minimum value in array(excluding zeros)
int minimum(int *a,int n)
{
    int i,min,index;
    min=100000;
    for(i=0;i<n;i++)
    {
        if(a[i]!=0 && a[i]<min)
        {
            min=a[i];
            index=i;
        }
    }
    return index;
}

//checks for the presence of a non-zero element in array
int check(int *a,int n)
{
    for(int i=0;i<n;i++)
    {
        if(a[i]!=0)
        return 1;
    }
    return 0;
}

//main function
int main()
{
    int n,j,k,max,min,slices;
    slices=0;
    scanf("%d",&n);
    int a[n];
    for(int j=0;j<n;j++)
    {
        scanf("%d",&a[j]);
    }
    //until all the elements of the array become 0
    //continue iterating to find slices
    while(check(a,n))
    {
        max=maximum(a,n);
        min=minimum(a,n);
        //if index of minimum value is greater than 
        //index of maximum value
        if(max<min)
        {
            slices=slices+1;
            for(j=0;j<n;j++)
            a[j]=0;
        }
        else
        {
            for(j=0;j<=min;j++)
            {
                a[j]=0;
            }
            slices=slices+1;
            if(check(a,n))
            {
                for(j=max;j<n;j++)
                {
                    a[j]=0;
                }
                slices=slices+1;
            }
        }
    }
    printf("slices %d",slices);
    return 0;
}

- SUKRITI BOHRA

Answer 3

与上面提出的解决方案相同，但在Python 3中实现：

def solution(A) -> int:
    if len(A) < 2:
        return len(A)

    stack = [A[0]]
    for num in A[1:]:
        if num >= stack[-1]:
            stack.append(num)
        else:
            smallest = stack.pop()
            while len(stack) > 0 and num < stack[-1]:
                stack.pop()
            stack.append(smallest)
    
    return len(stack)

- sheldonzy

Answer 4

这可以通过在MergeSort程序上进行串联来完成。

真正的操作发生在合并排序程序的合并阶段。

这里的想法是对于合并数组的任何索引i

1. 如果要添加的元素具有与插入索引相同的索引，则我们知道它形成了一个组，并将组计数增加1。

假设i/p = [1, 7, 5, 4, 2, 12]

我们创建一个新数组，用于存储元素的索引[0, 1, 2, 3, 4, 5, 6]

对于给定的输入，第一个合并函数将被调用以 左子数组=> 0 右子数组=> 1

对于新合并数组的第0个元素，我们查看可以使用哪个元素。

因此，对于新元素的第0个元素来自索引0，即1，它们是相同的，因此我们将组数增加1。索引1也是如此。

假设在合并数组中，对于索引i，需要插入索引j之后的元素，其中j > i，我们现在知道从i到j的子数组可以成为一组，如果合并数组中范围[i，j]内的所有元素都在此范围内。如果我们遇到另一个要添加的索引k，它大于j，我们将更新我们正在查找的索引以包括k，即[i，k]。因为，如果我们只考虑范围[i，j]，我们将在k处有一个元素，其中input[k]> input[j]，从而不形成有效的组。

例如，input = [3, 2, 0, 1]，它将变为[0, 1, 2, 3]，最后一次合并时，左子数组将是[1, 0]，右子数组将是[2, 3]。

对于合并数组的索引0，我们查看input[1]或input[2]中的最小值，即input[2]，索引为2，因此我们现在知道该数组的最小值来自索引2。我们继续查找直到合并数组的索引3，并更新贡献组的最高索引，并在两个索引相同时停止。

在索引1处，我们必须在索引1、3之间进行选择，然后发现索引[3]是下一个最小值，我们将最高索引更新为3，并继续直到合并索引的i等于要插入的元素的索引。

它运行在O(N log N)时间复杂度，并且我们得到的索引数组的结果是input数组的排序索引。

- thebenman

Answer 5

这个解决方案是O（N）的。但它只适用于具有不同数字的数组。

public static List<List<Integer>> countGroups(int[] arr) {

    List<List<Integer>> result = new ArrayList<List<Integer>>();

    if (arr.length < 1)
        return result;

    // create mins from right to left
    int[] mins = new int[arr.length];
    int tempMin = arr[arr.length - 1];
    for (int i = arr.length - 1; i >= 0; i--) {
        tempMin = Math.min(tempMin, arr[i]);
        mins[i] = tempMin;
    }

    // create max from left to right
    int[] maxs = new int[arr.length];
    int tempMax = arr[0];
    for (int i = 0; i < arr.length; i++) {
        tempMax = Math.max(tempMax, arr[i]);
        maxs[i] = tempMax;
    }

    // now that you have the start of intervals (mins) and end of intervals, you can
    // simply check if you are
    // still in the interval

    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < arr.length - 1; i++) {
        list.add(arr[i]);
        if (mins[i] != mins[i + 1] && maxs[i] != maxs[i + 1]) {
            result.add(new ArrayList<Integer>(list));
            list.clear();
        }
    }

    list.add(arr[arr.length - 1]);
    result.add(new ArrayList<Integer>(list));

    return result;
}

`

- Ramy Nazier

Answer 6

这是我能想到的解决方案。思路是在数组中保持一个活动索引，其值介于当前最大值和最小值之间。棘手的部分是要保持超出上下文的当前最大值作为currentCheckableMaxIndex，并且每当它恰好处于上下文中时，将其更改为currentMaxIndex。

public static int countSubArray(int[] A) {

    int len = A.length;
    int currentActiveIndex = 0;
    int count = 0;
    for(int i = 0; i < len;){
        int currentCheckableMaxIndex = i;
        int currentMinIndex = i, currentMaxIndex = i;
        for(int j = i; j < len; j++){
            // if there is a new min value, set its index,
            // also check if there is a checkable max that we can change to the new max
            if(A[currentMinIndex] > A[j]) {
                currentMinIndex = j;

                if(A[currentMaxIndex] < A[currentCheckableMaxIndex])
                    currentMaxIndex = currentCheckableMaxIndex;
            }
            // setting only the current checkable max to avoid including a max whose index is higher than current minimum
            // will only set it to the max index if there exists a new minimum whose index is > currentCheckableMaxIndex
            if(A[currentCheckableMaxIndex] < A[j]) {
                currentCheckableMaxIndex = j;
            }
            // save the current valid index only if the value in the current index is in between the current min and max
            if(A[currentMaxIndex] >= A[j] && A[j] >= A[currentMinIndex]) currentActiveIndex = j;
        }
        // i should continue from the current valid index + 1
        i = currentActiveIndex + 1;

        count++;

        // loop will not get here again if i == len - 1, so we count the last group that would have be omitted
        if(i == len - 1) {
            count++;
            break;
        }
    }

    return count;

}

- Tosin John