0

我目前正在为库存制作一个原始图形，显示当前占用了多少空间以及剩余多少空间。

它通过显示 5 行 20 个正方形（灰色 = 可用空间，黄色 = 占用空间）来做到这一点。

现在，我的问题是我想找到所有为 1 的值并将它们放在最后一个数组中。

这样数组来自：

var myMap:Array = [
            [1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
            [1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
            [1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0],
            [1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0],
            [1,0,0,0,0,0,1,1,0,1,1,0,0,1,1,0,0,0,0,0]
            ];

至

   var myMap:Array = [
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
            [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
            ];

基本上我想对整个数组进行排序，以便所有的零都排在第一位，所有的 1 都放在最后一个，直到它满了，然后是倒数第二个，依此类推。

我不在，我很可能需要一个算法来解决这个问题，但我希望有一种更简单的方法来做到这一点。我通常是 C# 开发人员，所以 AS3 不是我的强项。

希望有人理解我的意思并可以帮助我，现在是凌晨 4:30，所以我可能没有我想要的那么清醒。

~谢谢

编辑

添加了代码，以便人们可以获得更多信息：

请记住，大多数名称等都是占位符，目前我只需要它工作。

private function _showInventoryGraphic()
        {
            var mapWidth = 20;
            var mapHeight = 5;
            var myMap:Array = [
            [1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
            [1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
            [1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0],
            [1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0],
            [1,0,0,0,0,0,1,1,0,1,1,0,0,1,1,0,0,0,0,0]
            ];
            var posX:int = 15;
            var posY:int = 15;
            var startPosY:int = 250;
            for (var i:int=0; i<mapHeight; i++)
            {
                for (var u:int = 0; u < mapWidth; u++)
                {
                    if (myMap[i][u] == 0)
                    {
                        var grayRect:Shape = new Shape;
                        grayRect.graphics.beginFill(0x808080);
                        grayRect.graphics.drawRect(posX*u, startPosY, 10,10);
                        grayRect.graphics.endFill();
                        addChild(grayRect);
                    }
                    if (myMap[i][u] == 1)
                    {
                        var yellowRect:Shape = new Shape;
                        yellowRect.graphics.beginFill(0xFFFF00);
                        yellowRect.graphics.drawRect(posX*u, startPosY, 10,10);
                        yellowRect.graphics.endFill();
                        addChild(yellowRect);
                    }
                }
                startPosY += posY;
            }

        }
4

1 回答 1

2

在尝试了几种不同的方法之后，我认为最大的挑战是它是一个二维数组。

第一次尝试类似，但类似于快速排序，在二维数组的任一端都有 2 个指针，它们“向内”移动以寻找第一个指针为“1”而最后一个指针为“0”的场景并交换两者，直到指针在“中间”相遇。我放弃了这种方法，同时尝试正确地减少和增加二维数组中的线性计数器。=b

第二次尝试是跟踪数组中最后一个为空的索引和数组中最后一个已满的索引。然后在 addItem 和 removeItem 方法中，我将项目放在正确的位置并更新计数器以避免排序。这似乎有效，但可能有点混乱，将来可能更难维护。它将结果排序在单独的数组中。

在“直接排序”的第三次尝试中，我认为最简单的方法是将数组展平为二维数组，对其进行排序，然后重新加入它。你是对的，因为这不是最有效的方法，但要考虑的一件事是它需要多久运行一次，以及它真正需要多高效的上下文。我认为只有 100 个元素的二维数组对于使用低效的排序方法来说不是太大的问题？

也许其他人可以提出更好/更清洁的方法。=b

下面是我提到的代码。

第二次尝试（注意：我没有完全测试这个，但它似乎有效）：

import flash.geom.Point;

var unsortedMap:Array = [
                         [0,0,0,0,0,0,0,0,0,0],
                         [0,0,0,0,0,0,0,0,0,0],
                         [0,0,0,0,0,0,0,0,0,0],
                         [0,0,0,0,0,0,0,0,0,0],
                         [0,0,0,0,0,0,0,0,0,0]
                        ];

var sortedMap:Array = [
                         [0,0,0,0,0,0,0,0,0,0],
                         [0,0,0,0,0,0,0,0,0,0],
                         [0,0,0,0,0,0,0,0,0,0],
                         [0,0,0,0,0,0,0,0,0,0],
                         [0,0,0,0,0,0,0,0,0,0]
                        ];

var rowSize:int = unsortedMap[0].length;
var rowCount:int = unsortedMap.length;

// points to the last index at start, since want to have filled items at the 'end'
var emptySpotPointer:Point = new Point(rowSize - 1, rowCount - 1);
var fullSpotPointer:Point = new Point(rowSize - 1, rowCount - 1);

function print2dArray(prefix:String, input:Array):void {
    trace(prefix);
    for(var row:String in input){
        trace("\t"+ input[row]);
    }
    trace("");
}


function addItem(inputX:int, inputY:int):void {
    if(unsortedMap[inputY][inputX] == 1){
        trace("addItem() - Already an item here: "+ inputX +", "+ inputY);
        return;
    }
    trace("addItem() - Adding an item: "+ inputX +", "+ inputY);

    unsortedMap[inputY][inputX] = 1;
    sortedMap[emptySpotPointer.y][emptySpotPointer.x] = 1;
    fullSpotPointer.x = emptySpotPointer.x;
    fullSpotPointer.y = emptySpotPointer.y;

    if(emptySpotPointer.x == 0){
        emptySpotPointer.x = rowSize - 1;
        emptySpotPointer.y--;

    } else {
        emptySpotPointer.x--;
    }
}


function removeItem(inputX:int, inputY:int):void {
    if(unsortedMap[inputY][inputX] == 0){
        trace("removeItem() - No item here to remove: "+ inputX +", "+ inputY);
        return;
    }
    trace("removeItem() - Removing an item here: "+ inputX +", "+ inputY);

    unsortedMap[inputY][inputX] = 0;
    sortedMap[fullSpotPointer.y][fullSpotPointer.x] = 0;

    if(fullSpotPointer.x == (rowSize - 1)){
        fullSpotPointer.x = 0;
        fullSpotPointer.y++;

    } else {
        fullSpotPointer.x++;
    }
}



// testing stuff here
// -----------------------------------------------------------------
function addRandomitems():void {
    var randomX:int = Math.floor(Math.random() * rowSize);
    var randomY:int = Math.floor(Math.random() * rowCount);
    addItem(randomX, randomY);
}

function removeRandomitems():void {
    var randomX:int = Math.floor(Math.random() * rowSize);
    var randomY:int = Math.floor(Math.random() * rowCount);
    removeItem(randomX, randomY);
}

print2dArray("unsortedMap", unsortedMap);
print2dArray("sortedMap", sortedMap);

trace("Test: Adding items now ---------------------");
var counter:int = 0;
for(counter = 0; counter < 50; counter++){
    addRandomitems();
    print2dArray("unsortedMap", unsortedMap);
    print2dArray("sortedMap", sortedMap);
}

trace("Test: Removing items now ---------------------");
for(counter = 0; counter < 50; counter++){
    removeRandomitems();
    print2dArray("unsortedMap", unsortedMap);
    print2dArray("sortedMap", sortedMap);
}

第三次尝试：

import flash.utils.getTimer;

var myMap:Array = [
            [1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
            [1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
            [1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0],
            [1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0],
            [1,0,0,0,0,0,1,1,0,1,1,0,0,1,1,0,0,0,0,0]
            ];

function sort(inputArray:Array):Array {
    var rowSize:int = inputArray[0].length;

    var flat:Array = new Array();

    // flattening the array here
    for(var row:String in inputArray){
        flat = flat.concat(inputArray[row]);
    }
    flat.sort();

    var result:Array = new Array();

    // recreating the original array here by cutting out 'rowSize' chunks and reforming the 2d array
    while(flat.length > 0){
        result.push(new Array(flat.splice(0, rowSize)));
    }
    return result;
}

// testing
var startTimer:int = flash.utils.getTimer();
for(var counter:int = 0; counter < 10000; counter++){
    sort(myMap);
}

// Running the above 10,000 times takes 1836ms for me.
trace(flash.utils.getTimer() - startTimer);

// just to see the output:
trace(sort(myMap).join("\n"));
于 2013-06-11T05:50:09.090 回答