Javascript 检查一次交换后列表是否排序

Question

我想检查是否可以通过最多执行一次交换操作对列表进行排序，如果可以，我想 return true。不然我要returnfalse.

例如输入

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

应该得到 true 因为它已经排序了。

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

应该导致 true 因为交换一次，涉及 5 和 3，列表已排序。

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

应该导致 false，因为它需要不止一次交换才能排序。

我的代码如下。如果 A 已经排序，则 return 为真，但如果未排序但可以通过一次交换排序，则 return 为 undefined。

谁能帮我找出问题所在？

    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
               }
            }
        }
    }

我想检查每次交换后数组是否排序。我该怎么做？

Answer 1

如果不想对数组进行排序，最好统计arr[i] > arr[j] (j > i)的次数，如果count >= 1，则return .

将其用作辅助方法：

function isArraySorted(arr){
      for(var i = 0; i < arr.length ; ++i) {
          if(arr[i] > arr[i+1])
              return false;
       }

       return true;
}

这是你的新功能：

 function solution(A) {
     if (isArraySorted(A)) return true;

     for (var i = 0; i < A.length; i++) //if not sorted lets check
     {
         for (var j = i + 1; j < A.length; j++) {
             if (A[i] > A[j]) //swap only if A[i] > A[j]
             {
                 var temp = A[i];
                 A[i] = A[j];
                 A[j] = temp;
                 return isArraySorted(A); // after one swap check if it's sorted and return that value.
             }
         }
     }
 }

Answer 2

这应该符合您计划的目标

function solution(A) {
    // write your code in JavaScript (Node.js 0.12)
    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;
    } else {//swap once where its not in order
        for (var l = count+1; l<A.length;l++)
        {
            //Swap that and a subsequent element.
           var temp = A[count];
           A[count] = A[l];
           A[l] = temp;

           c = 0;
           for(var k=0; k<A.length; k++) //check if sorted
           {
              if(A[k] <= A[k+1])
                 c++;
              else
                 break;
            }
            if (c === A.length - 1) //if already sorted return true
            {
                 return true;
            }
            //Swap them back
            var temp = A[count];
            A[count] = A[l];
            A[l] = temp;
        }
    }
    return false;
}

Answer 3

see following example.
set it into a function. i used it in window onload

var a=[1,2,5,4,3];
var aTmp=a.slice(0);
aTmp.sort();
var cnt=0;
for(var i=0;i<a.length;i++){
   if(a[i]!=aTmp[i]){     
    cnt++;
   }
   if(cnt>2)
     return false;
}
if(cnt==0 || cnt==2)
    return true;
else
    return false;

Answer 4

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

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

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

的元素之前

现在我们向倒置对的右侧扫描至少与 x 一样大的最早元素。一旦我们找到这样一个元素，我们就取它之前的元素，并称这个元素为y。如果没有这样的元素，让 y 成为数组的最后一个元素。

如果数组可以一次交换排序，交换x和y是充分必要的。考虑案例：

如果反转对右边的所有元素都小于x，则需要将x移过所有元素。因此，我们将 x 与数组的最后一个元素交换。
否则，考虑x右边所有大于x的元素。在排序数组中，x 必须出现在所有元素之前，但 x 必须移过比它小的元素。因此，我们找到倒排对右侧最早的元素，该元素至少与 x 一样大，并将 x 交换到它之前的位置。

// 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 检查一次交换后列表是否排序

Javascript check if list is sorted after one swap

javascript

sorting

algorithm

swap