удаление дубликатов в отсортированном массиве

Question

На всякий случай вы пропустили вопрос об удалении дубликатов в массиве sorted. Которые могут применять очень быстрые алгоритмы (по сравнению с несортированными массивами) для удаления дубликатов.

• Вы можете пропустить это, если вы уже знаете, как работает удаление дубликатов в массивах SORTED

Пример:

var out=[];
for(var i=0,len=arr.length-1;i<len;i++){
    if(arr[i]!==arr[i+1]){
        out.push(arr[i]);
    }
}
out.push(arr[i]);

Видите? Это очень быстро. Я постараюсь объяснить, что только что произошло.

Сортированные массивы * могут выглядеть так:

arr=[0,1,1,2,2,3,4,5,5,6,7,7,8,9,9,9];

* сортировка может быть ASC или DESC, или другими странными методами, но важно то, что каждый дублирующийся элемент находится рядом друг с другом.

Мы остановились на array.length-1, потому что нам нечего проверять с

Затем мы добавили последний элемент независимо от всего, потому что:

кейс A:

... ,9,9,9];//we have dup(s) on the left of the last element

корпус B:

... ,7,9,10];//we don't have dup(s) on the left of the last element

Если вы действительно понимаете, что происходит, вы будете знать, что мы не добавили 9 в случае A. Поэтому мы хотим добавить последний элемент независимо от того, находимся ли мы в случае A или B.

---

Вопрос:

Это объясняет, я хочу сделать то же самое, но игнорирую значение undefined в таких случаях, как:

var arr=[];arr[99]=1;//0 through 98 are undefined, but do NOT hold the undefined value

Я хочу удалить их. И в случае, если у меня есть некоторые реальные undefined значения, они не должны быть удалены.

Вот моя неудачная попытка:

var out=[];
for (var i=0,len=arr.length; i < len - 1;) {
  var x = false;
  var y = false;

  for (var j = i, jo; j < len - 1; j++) {
    if (j in arr) {
      x = true;
      jo = arr[j];
      i = j + 1;
      break;
    }
  }
  if (x == false) {
    break;
  }

  for (var u = i, yo; u < len - 1; u++) {
    if (u in arr) {
      y = true;
      yo = arr[u];
      i = u + 1;
      break;
    }
  }
  if (y == false) {
    out.push(jo);
    break;
  }

  if (jo !== yo) {
    out.push(jo);
  }
}
out.push(arr[len - 1]);

Я действительно потерян, любая помощь приветствуется

Answer 1

Возможно что-то вроде этого:

var out = [],
    prev;

for(var i = 0; i < arr.length; i++) {
   if (!(i in arr))
      continue;

   if (arr[i] !== prev || out.length === 0) {
      out.push(arr[i]);
      prev = arr[i];
   }
}

Проверка out.length позволяет первому определенному элементу массива иметь значение undefined, когда prev также изначально начинается как undefined.

Обратите внимание, что в отличие от вашего исходного алгоритма, если arr пусто, это не будет помещать неопределенное значение в ваш массив out.

Или, если у вас достаточно новый браузер, вы можете использовать Array.forEach() метод , который выполняет итерацию только для элементов массива, которым присвоено значение.

Answer 2

Для начала, я не совсем уверен, что ваш оригинальный код кошерный.Мне кажется, что он может не работать, когда исходный список пуст, поскольку вы пытаетесь нажать последний элемент, несмотря ни на что.Это может быть лучше написано как:

var out = [];
var len = arr.length - 1;
if (len >= 0) {
    for (var i = 0;i < len; i++) {
        if (arr[i] !== arr[i+1]) {
            out.push (arr[i]);
        }
    }
    out.push (arr[len]);
}

Что касается вашего реального вопроса, я отвечу на это как алгоритм, так как я не знаю много JavaScript, но мне кажется, вы можете просто вспомнитьпоследний переданный номер, что-то вроде:

# Set up output array.

out = []

# Set up flag indicating first entry, and value of last added entry.

first = true
last = 0

for i = 0 to arr.length-1:
    # Totally ignore undefined entries (however you define that).

    if arr[i] is defined:
        if first:
            # For first defined entry in list, add and store it, flag non-first.

            out.push (arr[i])
            last = arr[i]
            first = false
        else:
            # Otherwise only store if different to last (and save as well).

            if arr[i] != last:
                out.push (arr[i])
                last = arr[i]

Answer 3

Это однострочник:

uniquify( myArray.filter(function(x){return true}) )

Если у вас еще не написано uniquify (функция, которую вы написали для удаления дубликатов), вы также можете использовать эту строку:

var newArray = [];
myArray.forEach(function(x) {
    if (newArray.length==0 || newArray.slice(-1)[0]!==x)
        newArray.push(x)
})

---

Разработка:

var a=[];
a[0]=1; a[1]=undefined; a[2]=undefined;
a[10]=2; a[11]=2;

Согласно OP, массив имеет "пять элементов", хотя a.length == 12. Хотя a [4] === не определено, он не является элементом массива по его определению и не должен включаться.

a.filter(function(x){return true}) превратит указанный массив в [1, undefined, undefined, 2, 2].

---

edit: Первоначально он был написан с .reduce() вместо .forEach(), но версия .forEach() с гораздо меньшей вероятностью может привести к проблемам с сборщиком мусора и передачей по значению в неэффективных реализациях JavaScript.

Для тех, кто обеспокоен совместимостью с 6-летним браузером MIE8, который не поддерживает последние два выпуска стандарта ECMAScript (и даже не полностью совместим с предыдущим), вы можете включить код в https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/forEach Однако, если кто-то обеспокоен совместимостью браузера, следует программировать через кросс-компилятор, такой как GWT. Если вы используете jQuery, вы также можете переписать вышеупомянутое, добавив всего несколько дополнительных символов, например $.forEach(array, ...).

Answer 4

Очень простая функция, входной массив должен быть отсортирован:

function removeDupes(arr) {
  var i = arr.length - 1;
  var o;
  var undefined = void 0;

  while (i > 0) {
    o = arr[i];

    // Remove elided or missing members, but not those with a 
    // value of undefined 
    if (o == arr[--i] || !(i in arr)) {
      arr.splice(i, 1);
    }
  }
  return arr;
}

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

Вот версия с прямым циклом:

function removeDupes2(arr) {
  var noDupes = [],
      o;

  for (var i=0, j=0, iLen=arr.length; i<iLen; i++) {
    o = arr[i];
    if (o != noDupes[j] && i in arr) {
       noDupes.push(o);
       j = noDupes.length - 1;
    }
  }
  return noDupes;
}

PS

Должен работать в любом браузере, поддерживающем javascript, без каких-либо дополнительных библиотек или исправлений.

Answer 5

Явным способом было бы упаковать массив ( удалить значения undefined) и использовать существующий алгоритм для дубликатов на этом ..

function pack(_array){
    var temp = [],
        undefined;
    for (i=0, len = _array.length; i< len; i++){
        if (_array[i] !== undefined){
            temp.push(_array[i]);
        }   
    }
    return temp;
}

Answer 6

Я думаю, это то, что вы хотите. Это довольно простой алгоритм.

var out = [], previous;
for(var i = 0; i < arr.length; i++) {
  var current = arr[i];
  if(!(i in arr)) continue;
  if(current !== previous) out.push(current);
  previous = arr[i];
}

Это будет выполняться в O(N) времени.

Answer 7

Этот код написан на javascript . Это очень просто.

Код:

function remove_duplicates(arr) {
        newArr = [];
        if (arr.length - 1 >= 0) {
            for (i = 0; i < arr.length - 1; i++) {
                // if current element is not equal to next
                // element then store that current element
                if (arr[i] !== arr[i + 1]) {
                    newArr.push(arr[i]);
                }
            }
            newArr.push(arr[arr.length - 1]);
        }
        return newArr
    }
    arr=[0,1,1,2,2,3,4,5,5,6,7,7,8,9,9,9];
    console.log(remove_duplicates(arr));

Answer 8

//sort the array
B.sort(function(a,b){ return a  - b});
//removing duplicate characters
    for(var i=0;i < B.length; i ++){
        if(B[i]==B[i + 1])
            B.splice(i,1)
    }

если элемент в следующем индексе и текущая позиция совпадают, удалить элемент в текущей позиции

splice(targetPosition,noOfElementsToBeRemoved)

Answer 9

ОК. Надеюсь, это не дубликат, но давайте предположим, что у вас есть отсортированный массив, и вы не можете использовать дополнительный массив для поиска и удаления дубликатов:

В Python

def findDup(arr, index=1, _index=0):

    if index >= len(arr):
        return

    if arr[index] != arr[_index]:

        findDup(arr, index+1, _index+1)

    if arr[index] == arr[_index]:
        arr = deletedup(arr, index)
        findDup(arr, index, _index) #Has to remain same here, because length has changed now



def deletedup(arr, del_index):
    del arr[del_index]
    return arr

arr = [1, 2, 3, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7]

findDup(arr)
print arr

Answer 10

Я считаю, что то, что вы пытаетесь достичь, не совсем возможно, но я могу ошибаться.

Это похоже на одну из тех классических проблем CS, как та, где парикмахер в деревне бреет только того, ктоне бритьсяЕсли вы установите значение элемента индекса массива как undefined, это на самом деле не undefined.Разве это не так?Значение может быть undefined, только если оно не было инициализировано.

Необходимо проверить, является ли значение null или undefined.Если null или дубликат пропустить значение, в противном случае сохраните его.

Если null значения и дубликаты - это то, что вы пытаетесь пропустить, то нижеприведенная функция поможет вам.

function  removeDuplicateAndNull(array){

    if(array.length==0)
        return [];

    var processed = [], previous=array[0];
    processed.push(array[0]);

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

        var value = array[i];

        if( typeof value !== 'undefined' && value ==null) 
            continue;

        if(value !== previous || typeof value === 'undefined')
            processed.push(value);

        previous = array[i];
    }
    return processed;
}

Тестовые случаи:

1. array=[,5,5,6,null,7,7] output =[ ,5,6,7]

2. array=[ 5,5,,6,null,,7,7] output=[5,,6,,7]

3. array=[7,7,,] output=[7,]

Но даже сэта функция есть предостережение.Если вы проверите третий тест, вывод будет [7,] вместо [7 ,,] !Если вы проверите длину входного и выходного массивов, array.length = 3 и output.length = 2.Предупреждение не о функции, а о самом JavaScript.