检查Javascript数组值是否按升序排列

Question

检查Javascript数组值是否按升序排列

11

假设我有一个Javascript整数数组，我想检查它的所有值是否按升序排列。我希望在算法发现一个低于（或等于）之前的任何值而不仅是比较直接前一个值时，将数组键保存在另一个数组中。

我所做的是这样的：

arr = [], nonvalid = [];

for (var j = 1; j < arr.length; j++){
    if ( arr[j+1] <= arr[j] ){
        nonvalid.push(j);
    }
}

显然上面的算法只检查比前一个值更低的值。

数组可能包含以下这些值：

arr = 1, 2, 3, 10, 5, 11, 12, 2, 4, 25

不合法的值是加粗的那些。如果我运行上面的循环，它将无法“捕获”倒数第二个值(4)，因为它高于其最近的左兄弟，但不高于其所有左兄弟。 编辑: 尝试了以下解决方案，除了我的之外，没有任何一种能正确地返回此数组的所有非有效值。:(

它们可以正确返回最后两个值，但不能返回第二个值。我不明白为什么。

[24398, 24397, 25004, 25177, 26302, 28036, 29312, 29635, 29829, 30476, 32595, 33732, 34995, 36047, 36363, 37310, 38022, 38882, 40746, 41212, 42846, 43588, 44029, 44595, 44846, 45727, 46041, 47293, 48002, 48930, 49858, 51184, 51560, 53895, 54247, 54614, 55713, 56813, 57282, 57480, 57875, 58073, 58403, 60321, 61469, 62051, 62310, 62634, 63217, 64505, 65413, 65677, 65940, 66203, 66572, 67957, 68796, 68964, 69098, 69233, 69435, 69759, 71496, 72577, 72823, 73007, 73252, 73743, 73866, 76405, 77037, 77416, 77669, 79691, 80885, 81339, 81794, 82067, 82431, 83244, 84861, 86836, 88632, 89877, 90296, 91049, 91885, 92351, 92614, 93141, 93733, 93930, 94531, 95206, 95882, 96895, 97732, 97973, 99261, 99422, 99583, 100332, 100599, 101666, 102066, 102600, 103504, 104432, 105174, 107216, 109085, 110181, 110679, 111177, 111988, 112553, 113005, 113457, 600, 600]

- Ricardus

2

那你能追踪最大值吗？ - Chris Moutray

最大值啊？有趣！让我试试看。 - Ricardus

9个回答

9

跟踪您所见过的最大值 (请参见fiddle)：

function find_invalid_numbers(arr) {
    var nonvalid, i, max;

    nonvalid = [];

    if (arr.length !== 0) {
        max = arr[0];

        for (i = 1; i < arr.length; ++i) {
            if (arr[i] < max) {
                nonvalid.push(arr[i]);
            } else {
                max = arr[i];
            }
        }
    }

    return nonvalid;
}

- cdhowie

4

为什么不与上一次已知的好数字进行比较呢？

var arr = [1, 2, 3, 10, 5, 11, 12, 2, 4, 25],
    nonvalid = [],
    lastGoodValue = 0;

for (var j = 1; j < arr.length; j++) {
    if (j && arr[j] <= lastGoodValue) {
        //if not the first number and is less than the last good value
        nonvalid.push(arr[j]);
    } else {
        //if first number or a good value
        lastGoodValue = arr[j];
    }
}

console.log(arr, nonvalid)

- Joseph

4

当你发现一个元素顺序错乱时，查看下一个元素，直到它们相对于错乱元素之前的元素不再错乱。

将错乱的元素添加到第二个数组中，并从新的有序元素继续。

var outs= [], L= A.length, i= 0, prev;
while(i<L){
    prev= A[i]; 
    while(A[++i]<prev) outs.push(i);
}
alert(outs)

- kennebec

哇！一个精致而简洁的 :) 它的工作效果非常好。而且它似乎比其他解决方案要求更少。 - Ricardus

1

演示

var arr = [24398, 24397, 25004, 25177, 26302, 28036, 29312, 29635, 29829, 30476, 32595, 33732, 34995, 36047, 36363, 37310, 38022, 38882, 40746, 41212, 42846, 43588, 44029, 44595, 44846, 45727, 46041, 47293, 48002, 48930, 49858, 51184, 51560, 53895, 54247, 54614, 55713, 56813, 57282, 57480, 57875, 58073, 58403, 60321, 61469, 62051, 62310, 62634, 63217, 64505, 65413, 65677, 65940, 66203, 66572, 67957, 68796, 68964, 69098, 69233, 69435, 69759, 71496, 72577, 72823, 73007, 73252, 73743, 73866, 76405, 77037, 77416, 77669, 79691, 80885, 81339, 81794, 82067, 82431, 83244, 84861, 86836, 88632, 89877, 90296, 91049, 91885, 92351, 92614, 93141, 93733, 93930, 94531, 95206, 95882, 96895, 97732, 97973, 99261, 99422, 99583, 100332, 100599, 101666, 102066, 102600, 103504, 104432, 105174, 107216, 109085, 110181, 110679, 111177, 111988, 112553, 113005, 113457, 600, 600],
    nonvalid = [],
    max = arr[0];

for(var j=0; j<arr.length; j++){
    var test= arr[j+1]<=max ? nonvalid.push(arr[j+1]) : max=arr[j];
}

alert(nonvalid); // 24397, 600, 600

- Roko C. Buljan

1

太正确了！感谢您的回答和分享！数组键中的+1只是缺失了。 - Ricardus

@Ricardus 不用谢！！这是一个非常有趣的问题！+1 - Roko C. Buljan

1

一个简单的功能性方法是内联完成，无需循环或变量：

arr.filter(function(a,b,c){
  return  Math.max.apply(Math, c.slice(0,b)) > a ;
});

- dandavis

1

您可以使用此示例中的map：

const ascendingArray = [1,2,3,4,5,6,7];
const descendingArray = [1,2,3,7,5,6,4]

const isAscending = array => array.map((a, i) => a > array[i + 1]).indexOf(true) === -1

console.log(isAscending(descendingArray)); // should be false
console.log(isAscending(ascendingArray)); // should be true

或者，您可以使用此示例中的filter：

const ascendingArray = [1,2,3,4,5,6,7];
const descendingArray = [1,2,3,7,5,6,4]

const isAscending = array => array.filter((a, i) => a > array[i + 1]).length === 0;

console.log(isAscending(ascendingArray)); // should be true
console.log(isAscending(descendingArray)); // should be false

- Titus Sutio Fanpula

0

在听取了您们的建议后，我尝试了以下算法来回答自己的问题。它似乎完成了工作，但有点过度设计。

for (var i = 0; i < arr.length; i++){

for (var j = 1; j < arr.length; j++){

    if ( arr[j] > 0 && arr[i] > 0 && j != i ){

        if ( arr[j] <= arr[i] && j > i ){

            if ( jQuery.inArray(j, nonvalid) == - 1) nonvalid.push(j);
        }
    }
} }

- Ricardus

0

首先复制数组，使用array.splice(index, 1)移除任何不按顺序的元素，然后继续操作。这样，任何元素都必须大于其前面的元素，但前一个元素始终是最大的。

- dave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Redu · Accepted Answer

还有一种非常好的功能方式可以做到这一点;

var isAscending = a => a.slice(1)
                        .map((e,i) => e > a[i])
                        .every(x => x);
                        
console.log(isAscending([1,2,3,4]));
console.log(isAscending([1,2,5,4]));

代码不错，但其中存在冗余。我们可以进一步简化，通过将.map()和.every()合并成一个来实现。

var isAscending = a => a.slice(1)
                        .every((e,i) => e > a[i]);
                        
console.log(isAscending([1,2,3,4]));
console.log(isAscending([1,2,5,4]));