Удалить дубликаты в массиве без использования коллекций. Java

#java #массивы #алгоритм #циклы

Необходимо удалить дубликаты в массиве без использования коллекций. 

C ArrayList или HashSet все понятно, тут делать не чего, но мне задание дали удалить
дубликаты не используя ничего, кроме массивов. При чем метод должен работать, даже
если дубликатов больше двух. 


Исходный массив {1 ,1, 1, 2, 1, 3, 3}
Искомый результат {1, 2, 3}


В общем уже голову сломал, может кто поможет?

Спасибо.
    

Ответы

Ответ 1

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

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] a = { 1, 1, 1, 2, 1, 3, 3 };

        int n = a.length;

        for ( int i = 0, m = 0; i != n; i++, n = m )
        {
            for ( int j = m = i + 1; j != n; j++ )
            {
                if ( a[j] != a[i] )
                {
                    if ( m != j ) a[m] = a[j];
                    m++;
                }
            }
        }


        if ( n != a.length )
        {
            int[] b = new int[n];
            for ( int i = 0; i < n; i++ ) b[i] = a[i];

            a = b;
        }

        for ( int x : a ) System.out.print( x + " " );
        System.out.println();
   }
}


Вывод программы

1 2 3


Ответ 2

int[] a = new int[] {1, 1, 1, 2, 1, 3, 3};
int[] b = new int[a.length];
int curIndex = 0;
for (int i: a) {
    if (!IntStream.range(0, curIndex).anyMatch(num - > b[num] == i)) {
        b[curIndex++] = i;
    }
}
System.out.println(Arrays.toString(Arrays.copyOf(b, curIndex))); //[1, 2, 3]


UPDATE

!IntStream.range(0, b.length).anyMatch(num - > b[num] == i)


можно заменить следующим методом

public static boolean contains(int[] a, int num) {
    for (int i in a) {
        if (i == num) {
            return true;
        }
    }
    return false;
}


И тогда основной for будет следующим

for (int i: a) {
    if (!contains(b, i))) {
        b[curIndex++] = i;
    }
}


Ответ 3

@Test
public void tt(){
    testArray(new int[]{1,2,3,4,5,5,5});
    testArray(new int[]{11,12,16,1,2,3,4});
    testArray(new int[]{3,3,3,3,3,3,3});
    testArray(new int[]{1});
    testArray(new int[]{});
    testArray(new int[]{10,11,11,11,11,11,11});
    testArray(new int[]{1,1,2,2,3,3,4,4});
}

public void testArray(int[] a){
    Arrays.sort(a);
    a = removeDuplicates(a);
    Arrays.stream(a).forEach(value -> System.out.print(value + " "));
    System.out.println();
}

public int[] removeDuplicates(int[] array){
    //Частные случаи
    if(array.length == 1) return array;
    if(array.length == 0) return new int[0];
    //
    //Размер больше 1, уникальное значение как минимум одно
    int unique = 1;
    for(int i = 1; i < array.length; i++){
        if(array[i] != array[i - 1]){
            unique++; //Если текущий с предыдущим не равны - значит
                      // увеличиваем счетчик уникальных значений
        }
    }
    int[] result = new int[unique]; //Новый массив нужного размера
    int k = 0; //Текущая позиция в новом массиве
    if(result.length > 0){
        result[k++] = array[0]; //Пишем в новый массив первое уникальное значение
    }
    for(int i = 1; i < array.length; i++){
        if(array[i] != array[i - 1]){
            result[k++] = array[i]; //Пишем в новый массив остальные уникальные значения
        }
    }
    return result;
}


Ответ 4

public void noDubs(){
    for (int i = 0; i
Ответ 5

Решил сдал. Завтра узнаем что мне педагог скажет вот такой вариант получился. Шапками
не кидать, я второй месяц занимаюсь. Всем большое спасибо за помощь, особенно простые
примеры навели на конструктивные мысли.

public class DuplicateWithoutCollection {

int nulls;

/**
 * Объединяет три метода.
 * @see #addNullInsteadDuplicate Добавление null вместо дкбликатов
 * @see #bubbleForNull(String[]) Сортировка null в конец массива
 * @see #deleteNulls(String[]) Перезапись всех null в новый массив
 * 

 *     Тест:
 * @see DuplicateWithoutCollectionTest#WhenArrayWithDuplicatesInThenArrayWithoutDuplicatesOut()
 */
public String[] finishDeleteDuplicate(String[] arr) {
    String[] addNull = addNullInsteadDuplicate(arr);
    String[] bubble = bubbleForNull(addNull);
    String[] deleteNull = deleteNulls(bubble);
    return deleteNull;
}

/**
 * Заменяет дубликаты на null
 * Записывает колличество нулей в переменну nulls
 * 

 *     Тест
 * @see DuplicateWithoutCollectionTest#WhenArrayWithDuplicateInThenArrayWithNullInsteadDupliateOut()
 */
public String[] addNullInsteadDuplicate(String[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] != null && arr[j] != null && arr[i].equals(arr[j])) {
                arr[j] = null;
                nulls++;
            }
        }
    }
    return arr;
}

/***
 * Выталкиват null в конец массива.
 * 

 *     Тест
 * @see DuplicateWithoutCollectionTest#WhenArrayWithNullInThenAllNullsGoToTheEndArray()
 */
public String[] bubbleForNull(String[] arr) {
    for (int i = arr.length - 1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] == null) {
                arr[j] = arr[j + 1];
                arr[j + 1] = null;
            }
        }
    }
    return arr;
}

/**
 * Удаляет нули.
 * 

 *     Тест
 * @see DuplicateWithoutCollectionTest#WhenArrayWithNullInThenArrayWithoutNullOut()
 * */
public String[] deleteNulls(String[] arr) {
    String[] result = new String[arr.length - this.nulls];
    for (int i = 0; i < result.length; i++) {
        result[i] = arr[i];
    }
    return result;
}


}