[1, 8, 5, 6, 10, 9, 11, 12];
我希望按升序对其进行排序,但是找出我需要排序的最大组数。在这个例子中,答案是:
[1], [8,5,6], [10,9], [11], [12]: so 5
[3, 2, 1]将变成1,因为整个数组需要排序。
我完全不知道如何做到这一点,希望能得到正确的方向提示。
[1, 8, 5, 6, 10, 9, 11, 12];
[1], [8,5,6], [10,9], [11], [12]: so 5
[3, 2, 1]将变成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();
}
这是一段适用于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;
}
与上面提出的解决方案相同,但在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)
这可以通过在MergeSort程序上进行串联来完成。
真正的操作发生在合并排序程序的合并阶段。
这里的想法是对于合并数组的任何索引i
假设i/p = [1, 7, 5, 4, 2, 12]
我们创建一个新数组,用于存储元素的索引[0, 1, 2, 3, 4, 5, 6]
对于给定的输入,第一个合并函数将被调用以 左子数组=> 0 右子数组=> 1
对于新合并数组的第0个元素,我们查看可以使用哪个元素。
因此,对于新元素的第0个元素来自索引0,即1,它们是相同的,因此我们将组数增加1。索引1也是如此。
例如,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
数组的排序索引。
这个解决方案是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;
}
`
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;
}