Javascript检查列表是否在一次交换后排序 [英] Javascript check if list is sorted after one swap

问题描述

我想检查是否可以通过执行最多一次交换操作来对列表进行排序，如果可以，我想返回true.否则，我想返回false.

I want to check if a list can be sorted by performing at most one swap operation, and I want to return true if it does. Otherwise, I want to return false.

例如输入

A = [1,2,3,4,5]

A = [1,2,3,4,5]

应该已生成true，因为它已被排序.

should result in true because it is already sorted.

A = [1,2,5,4,3]

A = [1,2,5,4,3]

应该导致true，因为一次交换(涉及5和3)将对列表进行排序.

should result in true because with one swap, involving 5 and 3, the list is sorted.

A = [1,2,5,3,4]

A = [1,2,5,3,4]

应生成false，因为它需要多个交换才能进行排序.

should result in false because it requires more than one swap to sort.

我的代码如下.如果A已经排序，则返回true，但是如果undefined没有排序但可以通过一次交换排序，则返回undefined.

My code is below. It returns true if A is already sorted, but it returns undefined if it is not sorted but can be sorted with one swap.

有人可以帮我找到问题吗?

Can someone help me find the problem?

    function solution(A) {
        var count=0;
        for(var k=0; k<A.length; k++) //check if sorted
        {
            if(A[k] <= A[k+1])
                count++;
            else
                break;
        }
        if (count === A.length - 1) //if already sorted return true
        {
            return true;
        }


        for(var i=0; i<A.length; i++)   //if not sorted lets check
        {
            var temp=0;
            for(var j=i+1; j<A.length; j++)
            {
               if(A[i] > A[j]) //swap only if A[i] > A[j]
               {
                    temp = A[i];
                    A[i] = A[j];
                    A[j] = temp;
//check if sorted
               }
            }
        }
    }

我想检查每次交换后是否对数组进行排序.我该怎么办?

I want to check if the array is sorted after every swap. How can I do that ?

推荐答案

尝试每种可能的交换并检查结果的幼稚方法相对于长度的O(n ³ )时间.大批.查找第一个无序对并尝试通过交换每个后续元素来修复它的更聪明的方法是花费O(n ² )时间.对数组进行排序并将其与原始数组进行比较的方法需要O(n log n)的时间.我们还能做得更好吗?

The naive approach that tries every possible swap and checks the result takes O(n³) time with respect to the length of the array. The smarter approach of finding the first out-of-order pair and trying to fix it by swapping in every subsequent element takes O(n²) time. The approach of sorting the array and comparing it to the original takes O(n log n) time. Can we do even better?

是的，我们可以在线性时间内解决此问题.我们从寻找一对相邻元素的倒置开始，这意味着左边的一个大于右边的一个.如果没有这样的对，则该数组已经排序.

Yes, we can solve this problem in linear time. We start by looking for an inverted pair of adjacent elements, meaning that the one on the left is bigger than the one on the right. If there is no such pair, the array is already sorted.

否则，我们找到最左边的一对.让我们采用这对中较大的元素，即左侧的元素，并将其命名为x.如果x是相等元素序列的最后一个元素，那么让我们选择最左边的元素，因为当我们将x与较小的元素y交换时，我们希望y出现在每个等于x的元素之前

Otherwise, we find the leftmost such pair. Let's take the larger element of this pair, namely the one on the left, and call it x. If x is the last of a sequence of equal elements, let's take the leftmost such element because when we swap x with a smaller element y, we want y to occur before every element equal to x.

现在，我们扫描到反向对的右边，寻找至少与x一样大的最早元素.找到这样的元素后，我们将紧接在它之前的元素称为y.如果没有这样的元素，则将y作为数组的最后一个元素.

Now we scan to the right of the inverted pair for the earliest element that is at least as big as x. Once we find such an element, we take the element immediately before it and call this element y. If there is no such element, let y be the last element of the array.

如果可以一次交换对数组进行排序，则交换x和y是必要且充分的.考虑以下情况:

If the array can be sorted in one swap, it is necessary and sufficient to swap x and y. Consider the cases:

• 如果反转对右边的所有元素都小于x，则必须将x移到所有元素之外.因此，我们将x与数组的最后一个元素交换.

• If all elements to the right of the inverted pair are smaller than x, it is necessary for x to be moved past all of them. Therefore, we swap x with the last element of the array.

否则，请考虑x右侧所有大于x的元素.在排序数组中，x必须在所有数组之前出现，但是x必须移到比其小的元素旁边.因此，我们在反向对的右边找到最早的元素，该元素至少与x一样大，然后将x交换到紧接它之前的位置.

Otherwise, consider all elements to the right of x that are bigger than x. In a sorted array, x must occur before all of them, but x must be moved past elements that are smaller than it. Therefore, we find the earliest element to the right of the inverted pair that is at least as big as x, and we swap x into the position immediately before it.

// Returns true if and only if A can be sorted with at most one swap.
function almostSorted(A) {
  for (var i = 1; i < A.length; ++i) {
    // Look for an inverted adjacent pair.
    if (A[i-1] <= A[i]) {
      continue;
    }
    var x = A[i-1],
        left = i-1;
    // If x is one of a sequence of identical elements, take the leftmost.
    while (left-1 >= 0 && A[left-1] == x) {
      --left;
    }
    // Scan past the inverted pair for the earliest element no smaller than x.
    for (++i; i < A.length; ++i) {
      if (A[i] >= x) {
        break;  // If we never break here, i will be equal to A.length.
      }
    }
    // Let y be the element before the earliest element no smaller than x.
    var right = i-1,
        y = A[right];  
    // Swap x and y.
    A[left] = y;
    A[right] = x;
    // Is the array sorted now?
    for (i = (left == 0 ? 1 : left); i < A.length; ++i) {
      if (A[i-1] > A[i]) {
        return false;
      }
    }
    return true;  // One swap was enough to sort the array.
  }
  return true;  // The array is already sorted.
}

// A few tests.
function test(A) {
  document.write('['+A.join(', ')+']');
  var result = almostSorted(A);
  document.write(': <span class="', result, '">', result, '</span>');
  if (result) {
    document.write(' &rarr; ', '['+A.join(', ')+']');
  }
  document.write('<br />');
}
test([1, 2, 5, 4, 3]);
test([1, 2, 3, 5, 4]);
test([1, 4, 3, 2, 5]);
test([1, 5, 4, 3, 2]);
test([1, 5, 3, 3, 7]);
test([2, 2, 1, 3, 7]);
test([2, 3, 1, 3, 7]);
test([1, 3, 1, 3, 7]);
test([2, 1, 1, 3, 7]);

body {
  font-family: sans-serif;
  font-size: 17px;
  color: #333;
}
.false {
  color: #b23c3c;
}
.true {
  color: #5c7b51;
}

这篇关于Javascript检查列表是否在一次交换后排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！