基于另一个充满“<”和“>”符号的数组排列数组

Arrange an array based on another array filled with “<” and “>” symbols

本文关键字：数组 符号 排列 另一个      更新时间：2023-09-26

我有两个数组。一个大小为n的数组由<和>符号填充。第二个数组的大小为n+1，具有整数。我必须以这样的方式排列第二个数组，使它能够满足第一个数组的条件。请注意，第一个数组不能修改。

conditionArray = ['>', '<', '<', '<', '>'];
numArray = [12, 9, 1, 11, 13, 2];

可能的输出:

[9, 1, 11, 12, 13, 2]

我有个想法:

1)对数据使用内置的排序方法。这满足conditionArray = ['<', '<', '<' ...]。

2)遍历conditionArray，对于每个>，取最后一个元素(最大的一个)，并将其插入当前索引中，移动每一个其他元素。否则，<已经满足，可以跳过。

在您的示例中，数组将经历以下中间状态:

12, 9, 1, 11, 13, 2 //start
1, 2, 9, 11, 12, 13 // initial sort
13, 1, 2, 8, 11, 12 // index 0 of condition is a > so insert the last element at index 0
13, 1, 2, 8, 11, 12 // < is NOP
13, 1, 2, 8, 11, 12 // < is NOP
13, 1, 2, 8, 11, 12 // < is NOP 
13, 1, 2, 8, 12, 11 // index 4 of condition is a > so insert the last element at index 4

一个非常基本的实现:

conditionArray = ['>', '<', '<', '<', '>'];
numArray = [12, 9, 1, 11, 13, 2];
numArray.sort( function(a, b) {return a -b ; /*lazy number comparison*/ });
console.log(numArray);
var size = numArray.length;
conditionArray.forEach( function(comparison, index) {
    //ignore '<'
    if (comparison == '>')
    {
        var finalElement = numArray[size - 1];
        numArray.splice(index, 0, finalElement); //insert the element
    }
    console.log(numArray);
        
});
numArray = numArray.slice(0, size); //remove all the extra stuff at the end
console.log(numArray);

这段代码大量使用插入。它可以很好地用于链接列表，因为插入是一个常数时间操作，但它不能很好地扩展到数组。如果插入的计算量很大(就像数组的典型情况一样)，则可以在辅助数组中一次只插入一个元素。

conditionArray = ['>', '<', '<', '<', '>'];
numArray = [12, 9, 1, 11, 13, 2];
numArray.sort( function(a, b) {return a - b; /*lazy number comparison*/ });
console.log(numArray);
var size = numArray.length;
var newArray = [];
var numInsertedFromBack = 0;
conditionArray.forEach( function(comparison, index) {
    if (comparison == '>')
    {
        var biggestElementNotAlreadyInserted = numArray[size - 1 - numInsertedFromBack];
        newArray.push(biggestElementNotAlreadyInserted);
        numInsertedFromBack += 1;
    }
    else {
        //just insert the next element
        //since we inserted stuff out of turn, we need 
        //to account for each skip, and backtrack that many times
        var smallestElementNotAlreadyInserted = numArray[index - numInsertedFromBack];
        newArray.push(smallestElementNotAlreadyInserted);
    }
    console.log(newArray);
});
//need to manually add the straggling final element
//since the comparisons are of array.length - 1
newArray.push(numArray[size - 1 - numInsertedFromBack]);
console.log(newArray);

conditionArray = ['>', '<', '<', '<', '>'];
numArray = [12, 9, 1, 11, 13, 2];
isComplete = false;
console.log(numArray);
 while (isComplete == false) {
  isComplete = true;
  for (i = 0; i < conditionArray.length; i++) {
   if ((conditionArray[i] == ">" && numArray[i] < numArray[i+1]) || (conditionArray[i] == "<" && numArray[i] > numArray[i+1])){
        isComplete = false;
        temp = numArray[i];
        numArray[i] = numArray[i+1];
        numArray[i+1] = temp;
      }
    }
  }
 document.write(numArray);
<!DOCTYPE html>
<html lan="en">
  <meta charset="utf-8">
  <body>
  </body>
</html>

相关文章：