Форум Flasher.ru - Поиск недостающего элемента в массиве

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Поиск недостающего элемента в массиве (http://www.flasher.ru/forum/showthread.php?t=207649)

Меньше чем в этом. А тот где сравнивается с in лучше чем Ваш, быстрее в несколько раз.

Код AS3:

var value:int = 0;

for (var i = 1; i <= n; i++) {

        value += i;

        if (i - 1 < array.length) value -= array[i - 1];

}

trace("Удаленное число " + value);

Цитата:

Сообщение от Akopalipsis (Сообщение 1164795)

А тот где сравнивается с in лучше чем Ваш, быстрее в несколько раз.

Ну так вы мой код и оптимизировали. А это уже командная работа.

Цитата:

Сообщение от Akopalipsis (Сообщение 1164795)

Меньше чем в этом. А тот где сравнивается с in лучше чем Ваш, быстрее в несколько раз.

вы сильно ошибаетесь в силу того, что не знаете как устроена работа indexOf.

запустите у себя код:

Код AS3:

var n:int = 1000000;

trace("N = " + n);

var array:Array = [];

for (var i:int = 1; i <= n; i++) {

        array.push(i);

}

 

var rand:int = Math.random() * n;

var num:int = array.splice(rand, 1);

trace("Удалили число " + num);

array.sort(function(...args):int {

        return Math.random() > 0.5 ? -1 : 1;

});

 

var t:Number = getTimer();

 

//1 способ

var value:Number = 0;

for (i = 1; i <= n; i++) {

        value += i;

        if (i - 1 < array.length) value -= array[i - 1];

}

 

trace("Удаленное число(1 способ) = " + value);

trace("time = " + (getTimer() - t));

 

t = getTimer();

 

//2 способ

for(i = 1; i <= array.length + 1; i++) {

        if(array.indexOf(i) < 0) {

                trace("Удаленное число(1 способ)  = " + i);

                trace("time = " + (getTimer() - t));

        }

}

Akopalipsis, я, конечно, не знаю насчёт in, но вот это

Код AS3:

var array:Array = [];

for(var j:int = 1; j <= 100; j ++)

        array.push(j);

array.splice(array.indexOf(3),1);

array.splice(array.indexOf(40),1);

 

trace(findMissingIntegers(array, 2));

 

function findMissingIntegers(arr:Array, missingNum:int = 0):Array

{

        var missingArr:Array = [];

 

        for(var i:int = 1; i <= arr.length + missingNum; i++)

        {

                if(!i in arr) missingArr.push(i);

        }

 

        return missingArr;

}

Не работает.

Код AS3:

var array:Array = [];

for(var j:int = 1; j <= 100; j ++)

        array.push(j);

array.splice(array.indexOf(3),1);

array.splice(array.indexOf(40),1);

 

trace(findMissingIntegers(array, 2));

 

function findMissingIntegers(arr:Array, missingNum:int = 0):Array

{

        var missingArr:Array = [];

 

        for(var i:int = 1; i <= arr.length + missingNum; i++)

        {

                if(!(i in arr)) missingArr.push(i);

        }

 

        return missingArr;

}

Это выдаёт 98, 99, 100,

Код AS3:

var array:Array = [];

for(var j:int = 1; j <= 100; j ++)

        array.push(j);

array.splice(array.indexOf(3),1);

array.splice(array.indexOf(40),1);

 

trace(findMissingIntegers(array, 2));

 

function findMissingIntegers(arr:Array, missingNum:int = 0):Array

{

        var missingArr:Array = [];

 

        for(var i:int = 1; i <= arr.length + missingNum; i++)

        {

                if(arr.indexOf(i) < 0) missingArr.push(i);

        }

 

        return missingArr;

}

А это работает как положено и выдаёт 3 и 40.

Добавлено через 13 минут
Вот, в общем, самый найменее громоздкий и простой для понимания код, а главное работающий, по поиску удалённых чисел.

Код AS3:

function findMissingIntegers(arr:Array, missingNum:int = 0):Array

{

        var missingArr:Array = [];

        for(var i:int = 1; i <= arr.length + missingNum; i++)

                if(arr.indexOf(i) < 0) missingArr.push(i);

        return missingArr;

}

Вот, если прибегать к формуле арифметической прогрессии:

Код AS3:

private function find(list:Array):int

{

        var summ:int;

        var len:int = list.length + 1;

        for (var i:int = 0; i < len - 1; ++i) summ += list[i];

        return (((1+len)/2) * len) - summ;

}

Цитата:

Сообщение от toFL (Сообщение 1164809)

Вот, если прибегать к формуле арифметической прогрессии:

Код AS3:

private function find(list:Array):int

{

        var summ:int;

        var len:int = list.length;

        for (var i:int = 0; i < len; ++i) summ += list[i];

        return (((1+len)/2) * len) - summ;

}

Вот это

Код AS3:

var array:Array = [];

for(var j:int = 1; j <= 100; j ++)

        array.push(j);

array.splice(array.indexOf(40),1);

 

trace(findMissingIntegers(array, 1));

trace(find(array));

 

function find(list:Array):int

{

        var summ:int;

        var len:int = list.length;

        for (var i:int = 0; i < len; ++i) summ += list[i];

        return (((1+len)/2) * len) - summ;

}

 

function findMissingIntegers(arr:Array, missingNum:int = 0):Array

{

        var missingArr:Array = [];

        for(var i:int = 1; i <= arr.length + missingNum; i++)

                if(arr.indexOf(i) < 0) missingArr.push(i);

        return missingArr;

}

у меня выбивает

Код:

40

-60

Обновил пост, забыл ++ поставить. Проверяй.

Пример со встряхиванием массива:

Код AS3:

var arr:Array = [];

for (var j:int = 1; j <= 100; j ++)

{

        arr.push(j);

}

 

var array:Array = arrayShuffle(arr);

trace(array);

 

array.splice(array.indexOf(40),1);

 

 

trace(findMissingIntegers(array, 1));

trace(find(array));

 

function find(list:Array):int

{

        var summ:int;

        var len:int = list.length + 1;

        for (var i:int = 0; i < list.length; i++)

        {

                summ +=  list[i];

        }

        return (((1+len)/2) * len) - summ;

}

 

function findMissingIntegers(arr:Array, missingNum:int = 0):Array

{

        var missingArr:Array = [];

        for (var i:int = 1; i <= arr.length + missingNum; i++)

                if (arr.indexOf(i) < 0) missingArr.push(i);

        return missingArr;

}

 

function arrayShuffle(arr:Array):Array

{

        var newArr:Array = [];

        while (arr.length > 0)

        {

                newArr.push(arr.splice(Math.round(Math.random() * (arr.length - 1)), 1)[0]);

        }

        return newArr;

}

SuriTheAngel вы были правы! С in не работает, так-как in показывает ключи.
я почему-то думал что в массивах он показывает элементы.
toFL Огромное Вам Спасибо! Лучше кода и быть не может.

Вот вам ещё один способ поиска удалённых чисел, но его недостаток в том, что если отсутствует последнее число, то этого он не замечает, ибо настоятельно длина предыдущего массива не задаётся(хотя если это обязательно, то можно и сделать так)
Без indexOf.

Код AS3:

function findAllMissedIntegers(arr:Array):Array

{

        arr.sort(Array.NUMERIC);

        var missingArr:Array = [];

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

        {

                if((arr[i] + 1) != (arr[i + 1]) && arr[i + 1]) 

                {

                        arr.splice(i + 1, 0, arr[i] + 1);

                        missingArr.push(arr[i + 1]);

                }

        }

        return missingArr;

}