Как эффективно удалять дубликаты из массива без использования Set

Ответ 1

Поскольку этот вопрос все еще получает много внимания, я решил ответить на него, скопировав этот ответ из Code Review.SE:

Вы придерживаетесь той же философии, что и тип пузыря, который очень, очень, очень медленно. Вы пробовали это?:

• Сортируйте неупорядоченный массив с quicksort. Быстрая сортировка намного быстрее чем сортировка пузырьков (я знаю, вы не сортируете, но алгоритм вы follow - почти то же самое, что и сортировка пузырьков для перемещения массива).

• Затем начните удаление дубликатов (повторяющиеся значения будут рядом с каждым Другие). В цикле for вы можете иметь два индекса: source и destination. (На каждом цикле вы копируете source в destination, если они не одинаковы и увеличиваются как на 1). Каждый раз, когда вы находите дублируйте, вы увеличиваете источник (и не выполняете копию). @morgano

Ответ 2

вы можете взять справку Установить коллекцию

int end = arr.length;
Set<Integer> set = new HashSet<Integer>();

for(int i = 0; i < end; i++){
  set.add(arr[i]);
}

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

Iterator it = set.iterator();
while(it.hasNext()) {
  System.out.println(it.next());
}

Ответ 3

Примечание: я предполагаю, что массив отсортирован.

Код:

int[] input = new int[]{1, 1, 3, 7, 7, 8, 9, 9, 9, 10};
int current = input[0];
boolean found = false;

for (int i = 0; i < input.length; i++) {
    if (current == input[i] && !found) {
        found = true;
    } else if (current != input[i]) {
        System.out.print(" " + current);
        current = input[i];
        found = false;
    }
}
System.out.print(" " + current);

выход:

  1 3 7 8 9 10

Ответ 4

Поскольку вы можете предположить, что диапазон находится в диапазоне от 0 до 1000, существует очень простое и эффективное решение

//Throws an exception if values are not in the range of 0-1000
public static int[] removeDuplicates(int[] arr) {
    boolean[] set = new boolean[1001]; //values must default to false
    int totalItems = 0;

    for (int i = 0; i < arr.length; ++i) {
        if (!set[arr[i]]) {
            set[arr[i]] = true;
            totalItems++;
        }
    }

    int[] ret = new int[totalItems];
    int c = 0;
    for (int i = 0; i < set.length; ++i) {
        if (set[i]) {
            ret[c++] = i;
        }
    }
    return ret;
}

Это выполняется в линейном времени O (n). Caveat: возвращенный массив сортируется, поэтому, если это незаконно, этот ответ недействителен.

Ответ 5

Незначительное изменение самого исходного кода путем удаления самого внутреннего для цикла.

public static int[] removeDuplicates(int[] arr){
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            if (arr[i] == arr[j]) {                  
                /*int shiftLeft = j;
                for (int k = j+1; k < end; k++, shiftLeft++) {
                    arr[shiftLeft] = arr[k];
                }*/
                arr[j] = arr[end-1];
                end--;
                j--;
            }
        }
    }

    int[] whitelist = new int[end];
    /*for(int i = 0; i < end; i++){
        whitelist[i] = arr[i];
    }*/
    System.arraycopy(arr, 0, whitelist, 0, end);
    return whitelist;
}

Ответ 6

class Demo 
{
    public static void main(String[] args) 
    {
        int a[]={3,2,1,4,2,1};
        System.out.print("Before Sorting:");
        for (int i=0;i<a.length; i++ )
        {
            System.out.print(a[i]+"\t");
        }
        System.out.print ("\nAfter Sorting:");
        //sorting the elements
        for(int i=0;i<a.length;i++)
        {
            for(int j=i;j<a.length;j++)
            {
                if(a[i]>a[j])
                {
                    int temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }

            }
        }

        //After sorting
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]+"\t");
        }
        System.out.print("\nAfter removing duplicates:");
        int b=0;
        a[b]=a[0];
        for(int i=0;i<a.length;i++)
        {
            if (a[b]!=a[i])
            {
                b++;
                a[b]=a[i];
            }
        }
        for (int i=0;i<=b;i++ )
        {
            System.out.print(a[i]+"\t");
        }
    }
}
  OUTPUT:Before Sortng:3 2 1 4 2 1 After Sorting:1 1 2 2 3 4 
                Removing Duplicates:1 2 3 4

Ответ 7

Существует много решений этой проблемы.

• Подход к сортировке

  • Вы сортируете свой массив и разрешаете только уникальные элементы

• Установленный подход

  • Вы объявляете HashSet, где вы кладете все предметы, тогда у вас есть только уникальные.

• Вы создаете логический массив, который представляет все готовые элементы, (это зависит от ваших данных в массиве).

Если вы имеете дело с большим объемом данных, я бы выбрал решение 1.. Поскольку вы не выделяете дополнительную память, а сортировка выполняется довольно быстро. Для небольшого набора данных сложность будет n ^ 2, но для больших я будет n log n.

Ответ 8

Что делать, если вы создаете два булевых массива: 1 для отрицательных значений и 1 для положительных значений и инициализируете все это на false.

Затем вы производите цикл ввода входного массива и поиск в массивах, если вы уже активировали значение. Если нет, добавьте его в выходной массив и пометьте его как уже использованный.

Ответ 9

public static int[] removeDuplicates(int[] arr){
    HashSet<Integer> set = new HashSet<>();
    final int len = arr.length;
    //changed end to len
    for(int i = 0; i < len; i++){
        set.add(arr[i]);
    }

    int[] whitelist = new int[set.size()];
    int i = 0;
    for (Iterator<Integer> it = set.iterator(); it.hasNext();) {
        whitelist[i++] = it.next();
    }
    return whitelist;
}

Работает за время O (N) вместо времени O (N ^ 3)

Ответ 10

Это простой способ сортировки элементов в массиве

public class DublicatesRemove {
    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("enter size of the array");
        int l = Integer.parseInt(br.readLine());
        int[] a = new int[l];
        // insert elements in the array logic
        for (int i = 0; i < l; i++) 
        {
            System.out.println("enter a element");
            int el = Integer.parseInt(br.readLine());
            a[i] = el;
        }
        // sorting elements in the array logic
        for (int i = 0; i < l; i++) 
        {
            for (int j = 0; j < l - 1; j++) 
            {
                if (a[j] > a[j + 1])
                {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        // remove duplicate elements logic
        int b = 0;
        a[b] = a[0];
        for (int i = 1; i < l; i++)
        {
            if (a[b] != a[i])
            {
                b++;
                a[b]=a[i];

            }

        }
        for(int i=0;i<=b;i++)
        {
            System.out.println(a[i]);
        }


    }
}

Ответ 11

package com.pari.practice;

import java.util.HashSet;
import java.util.Iterator;

import com.pari.sort.Sort;

public class RemoveDuplicates {

 /**
 * brute force- o(N square)
 * 
 * @param input
 * @return
 */
public static int[] removeDups(int[] input){
    boolean[] isSame = new boolean[input.length];
    int sameNums = 0;

    for( int i = 0; i < input.length; i++ ){
        for( int j = i+1; j < input.length; j++){
            if( input[j] == input[i] ){ //compare same
                isSame[j] = true;
                sameNums++;
            }
        }
    }

    //compact the array into the result.
    int[] result = new int[input.length-sameNums];
    int count = 0;
    for( int i = 0; i < input.length; i++ ){
        if( isSame[i] == true) {
            continue;
        }
        else{
            result[count] = input[i];
            count++;
        }
    }

    return result;
}

/**
 * set - o(N)
 * does not guarantee order of elements returned - set property
 * 
 * @param input
 * @return
 */
public static int[] removeDups1(int[] input){
    HashSet myset = new HashSet();

    for( int i = 0; i < input.length; i++ ){
        myset.add(input[i]);
    }

    //compact the array into the result.
    int[] result = new int[myset.size()];
    Iterator setitr = myset.iterator();
    int count = 0;
    while( setitr.hasNext() ){
        result[count] = (int) setitr.next();
        count++;
    }

return result;
}

/**
 * quicksort - o(Nlogn)
 * 
 * @param input
 * @return
 */
public static int[] removeDups2(int[] input){
    Sort st = new Sort();
    st.quickSort(input, 0, input.length-1); //input is sorted

    //compact the array into the result.
    int[] intermediateResult = new int[input.length];
    int count = 0;
    int prev = Integer.MIN_VALUE;
    for( int i = 0; i < input.length; i++ ){
        if( input[i] != prev ){
            intermediateResult[count] = input[i];
            count++;
        }
        prev = input[i];
    }

    int[] result = new int[count];
    System.arraycopy(intermediateResult, 0, result, 0, count);

    return result;
}


public static void printArray(int[] input){
    for( int i = 0; i < input.length; i++ ){
        System.out.print(input[i] + " ");
    }
}

public static void main(String[] args){
    int[] input = {5,6,8,0,1,2,5,9,11,0};
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups(input));
    System.out.println();
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups1(input));
    System.out.println();
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups2(input));
}
}

Вывод: 5 6 8 0 1 2 9 11

0 1 2 5 6 8 9 11

0 1 2 5 6 8 9 11

Я только что написал вышеуказанный код для тестирования. спасибо.

Ответ 12

Вам нужно отсортировать массив, а затем цикл и удалить дубликаты. Поскольку вы не можете использовать другие инструменты, вам нужно написать код самостоятельно.

Вы можете легко найти примеры quicksort в Java в Интернете (на котором основан этот пример).

public static void main(String[] args) throws Exception {
    final int[] original = new int[]{1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1};
    System.out.println(Arrays.toString(original));
    quicksort(original);
    System.out.println(Arrays.toString(original));
    final int[] unqiue = new int[original.length];
    int prev = original[0];
    unqiue[0] = prev;
    int count = 1;
    for (int i = 1; i < original.length; ++i) {
        if (original[i] != prev) {
            unqiue[count++] = original[i];
        }
        prev = original[i];
    }
    System.out.println(Arrays.toString(unqiue));
    final int[] compressed = new int[count];
    System.arraycopy(unqiue, 0, compressed, 0, count);
    System.out.println(Arrays.toString(compressed));
}

private static void quicksort(final int[] values) {
    if (values.length == 0) {
        return;
    }
    quicksort(values, 0, values.length - 1);
}

private static void quicksort(final int[] values, final int low, final int high) {
    int i = low, j = high;
    int pivot = values[low + (high - low) / 2];
    while (i <= j) {
        while (values[i] < pivot) {
            i++;
        }
        while (values[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(values, i, j);
            i++;
            j--;
        }
    }
    if (low < j) {
        quicksort(values, low, j);
    }
    if (i < high) {
        quicksort(values, i, high);
    }
}

private static void swap(final int[] values, final int i, final int j) {
    final int temp = values[i];
    values[i] = values[j];
    values[j] = temp;
}

Итак, процесс выполняется за 3 шага.

• Сортировка массива - O(nlgn)
• Удалить дубликаты - O(n)
• Компактный массив - O(n)

Таким образом, это значительно улучшает ваш подход O(n^3).

Вывод:

[1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1]
[1, 1, 1, 2, 4, 4, 7, 8, 8, 9, 9]
[1, 2, 4, 7, 8, 9, 0, 0, 0, 0, 0]
[1, 2, 4, 7, 8, 9]

ИЗМЕНИТЬ

Значения состояний OP внутри массива не имеют значения. Но я могу предположить, что диапазон находится между 0-1000. Это классический случай, когда можно использовать сортировку O (n).

Мы создаем массив размером range +1, в данном случае 1001. Затем мы перебираем данные и увеличиваем значения по каждому индексу, соответствующему datapoint.

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

public static void main(String[] args) throws Exception {
    final int[] original = new int[]{1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1, 1000, 1000};
    System.out.println(Arrays.toString(original));
    final int[] buckets = new int[1001];
    for (final int i : original) {
        buckets[i]++;
    }
    final int[] unique = new int[original.length];
    int count = 0;
    for (int i = 0; i < buckets.length; ++i) {
        if (buckets[i] > 0) {
            unique[count++] = i;
        }
    }
    final int[] compressed = new int[count];
    System.arraycopy(unique, 0, compressed, 0, count);
    System.out.println(Arrays.toString(compressed));
}

Вывод:

[1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1, 1000, 1000]
[1, 2, 4, 7, 8, 9, 1000]

Ответ 13

Для отсортированного массива просто проверьте следующий индекс:

//sorted data!
public static int[] distinct(int[] arr) {
    int[] temp = new int[arr.length];

    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        int current = arr[i];

        if(count > 0 )
            if(temp[count - 1] == current)
                continue;

        temp[count] = current;
        count++;
    }

    int[] whitelist = new int[count];
    System.arraycopy(temp, 0, whitelist, 0, count);

    return whitelist;
}

Ответ 14

public static void main(String args[]) {
    int[] intarray = {1,2,3,4,5,1,2,3,4,5,1,2,3,4,5};

    Set<Integer> set = new HashSet<Integer>();
    for(int i : intarray) {
        set.add(i);
    }

    Iterator<Integer> setitr = set.iterator();
    for(int pos=0; pos < intarray.length; pos ++) {
        if(pos < set.size()) {
            intarray[pos] =setitr.next();
        } else {
            intarray[pos]= 0;
        }
    }

    for(int i: intarray)
    System.out.println(i);
}

Ответ 15

Я знаю, что это немного мертво, но я просто написал это для своего собственного использования. Это более или менее то же самое, что и добавление в хэшсет, а затем вытягивание всех элементов из него. Он должен работать в худшем случае O (nlogn).

    public static int[] removeDuplicates(int[] numbers) {
    Entry[] entries = new Entry[numbers.length];
    int size = 0;
    for (int i = 0 ; i < numbers.length ; i++) {
        int nextVal = numbers[i];
        int index = nextVal % entries.length;
        Entry e = entries[index];
        if (e == null) {
            entries[index] = new Entry(nextVal);
            size++;
        } else {
            if(e.insert(nextVal)) {
                size++;
            }
        }
    }
    int[] result = new int[size];
    int index = 0;
    for (int i = 0 ; i < entries.length ; i++) {
        Entry current = entries[i];
        while (current != null) {
            result[i++] = current.value;
            current = current.next;
        }
    }
    return result;
}

public static class Entry {
    int value;
    Entry next;

    Entry(int value) {
        this.value = value;
    }

    public boolean insert(int newVal) {
        Entry current = this;
        Entry prev = null;
        while (current != null) {
            if (current.value == newVal) {
                return false;
            } else if(current.next != null) {
                prev = current;
                current = next;
            }
        }
        prev.next = new Entry(value);
        return true;
    }
}

Ответ 16

int tempvar=0; //Variable for the final array without any duplicates
     int whilecount=0;    //variable for while loop
     while(whilecount<(nsprtable*2)-1) //nsprtable can be any number
     {
//to check whether the next value is idential in case of sorted array       
if(temparray[whilecount]!=temparray[whilecount+1])
        {
            finalarray[tempvar]=temparray[whilecount];
            tempvar++;
            whilecount=whilecount+1;
        }
        else if (temparray[whilecount]==temparray[whilecount+1])
        {
            finalarray[tempvar]=temparray[whilecount];
            tempvar++;
            whilecount=whilecount+2;
        }
     }

Надеюсь, что это поможет или решит цель.

Ответ 17

Не очень интересно обновлять пользовательский ввод, однако учитывая ваши ограничения...

public int[] removeDup(int[] nums) {
  Arrays.sort(nums);
  int x = 0;
  for (int i = 0; i < nums.length; i++) {
    if (i == 0 || nums[i] != nums[i - 1]) {
    nums[x++] = nums[i];
    }
  }
  return Arrays.copyOf(nums, x);
}

Сортировка массива может быть легко заменена любым алгоритмом nlog (n).

Ответ 18

public static void main(String[] args) {
        Integer[] intArray = { 1, 1, 1, 2, 4, 2, 3, 5, 3, 6, 7, 3, 4, 5 };
        Integer[] finalArray = removeDuplicates(intArray);
        System.err.println(Arrays.asList(finalArray));
    }

    private static Integer[] removeDuplicates(Integer[] intArray) {
        int count = 0;
        Integer[] interimArray = new Integer[intArray.length];
        for (int i = 0; i < intArray.length; i++) {
            boolean exists = false;
            for (int j = 0; j < interimArray.length; j++) {
                if (interimArray[j]!=null && interimArray[j] == intArray[i]) {
                    exists = true;
                }
            }
            if (!exists) {
                interimArray[count] = intArray[i];
                count++;
            }
        }
        final Integer[] finalArray = new Integer[count];
        System.arraycopy(interimArray, 0, finalArray, 0, count);
        return finalArray;
    }

Ответ 19

Я чувствую, что идея Android Killer отличная, но мне просто интересно, можем ли мы использовать HashMap. Поэтому я сделал небольшой эксперимент. И я обнаружил, что HashMap кажется быстрее, чем HashSet.

Вот код:

    int[] input = new int[1000000];

    for (int i = 0; i < input.length; i++) {
        Random random = new Random();
        input[i] = random.nextInt(200000);
    }

    long startTime1 = new Date().getTime();
    System.out.println("Set start time:" + startTime1);

    Set<Integer> resultSet = new HashSet<Integer>();

    for (int i = 0; i < input.length; i++) {
        resultSet.add(input[i]);
    }

    long endTime1 = new Date().getTime();
    System.out.println("Set end time:"+ endTime1);
    System.out.println("result of set:" + (endTime1 - startTime1));     
    System.out.println("number of Set:" + resultSet.size() + "\n");

    long startTime2 = new Date().getTime();
    System.out.println("Map start time:" + startTime1);

    Map<Integer, Integer> resultMap = new HashMap<Integer, Integer>();

    for (int i = 0; i < input.length; i++) {
        if (!resultMap.containsKey(input[i]))
            resultMap.put(input[i], input[i]);
    }

    long endTime2 = new Date().getTime();
    System.out.println("Map end Time:" + endTime2);
    System.out.println("result of Map:" + (endTime2 - startTime2));
    System.out.println("number of Map:" + resultMap.size());

Вот результат:

Set start time:1441960583837
Set end time:1441960583917
result of set:80
number of Set:198652

Map start time:1441960583837
Map end Time:1441960583983
result of Map:66
number of Map:198652

Ответ 20

Это не использование Set, Map, List или любой дополнительной коллекции, только два массива:

package arrays.duplicates;

import java.lang.reflect.Array;
import java.util.Arrays;

public class ArrayDuplicatesRemover<T> {

    public static <T> T[] removeDuplicates(T[] input, Class<T> clazz) {
        T[] output = (T[]) Array.newInstance(clazz, 0);
        for (T t : input) {
            if (!inArray(t, output)) {
                output = Arrays.copyOf(output, output.length + 1);
                output[output.length - 1] = t;
            }
        }
        return output;
    }

    private static <T> boolean inArray(T search, T[] array) {
        for (T element : array) {
            if (element.equals(search)) {
                return true;
            }
        }
        return false;
    }

}

И главное проверить его

package arrays.duplicates;

import java.util.Arrays;

public class TestArrayDuplicates {

    public static void main(String[] args) {
        Integer[] array = {1, 1, 2, 2, 3, 3, 3, 3, 4};
        testArrayDuplicatesRemover(array);
    }

    private static void testArrayDuplicatesRemover(Integer[] array) {
        final Integer[] expectedResult = {1, 2, 3, 4};
        Integer[] arrayWithoutDuplicates = ArrayDuplicatesRemover.removeDuplicates(array, Integer.class);
        System.out.println("Array without duplicates is supposed to be: " + Arrays.toString(expectedResult));
        System.out.println("Array without duplicates currently is: " + Arrays.toString(arrayWithoutDuplicates));
        System.out.println("Is test passed ok?: " + (Arrays.equals(arrayWithoutDuplicates, expectedResult) ? "YES" : "NO"));
    }

}

И вывод:

Array without duplicates is supposed to be: [1, 2, 3, 4]
Array without duplicates currently is: [1, 2, 3, 4]
Is test passed ok?: YES

Ответ 21

Как насчет этого, только для отсортированного массива чисел, для печати массива без дубликатов, без использования Set или других коллекций, просто Array:

 public static int[] removeDuplicates(int[] array) {
    int[] nums =new int[array.length];
    int addedNum = 0;
    int j=0;
    for(int i=0;i<array.length;i++) {
        if (addedNum != array[i]) {
        nums[j] = array[i];
        j++;
        addedNum = nums[j-1];
        }
    }
    return Arrays.copyOf(nums, j);
}

Массив из 1040 дублированных чисел, обработанных в 33020 наносекундах (0,033020 миллисекунд).

Ответ 22

Хорошо, поэтому вы не можете использовать Set или другие коллекции. Одно из решений, которое я пока не вижу здесь, основан на использовании Bloom filter, который по существу представляет собой массив бит, поэтому возможно, это соответствует вашим требованиям.

Фильтр Bloom - это прекрасная и очень удобная техника, быстрая и экономичная по площади, которая может быть использована для быстрой проверки существования элемента в наборе без сохранения самого набора или элементов. Он имеет (как правило, малую) ложноположительную ставку, но не имеет ложной отрицательной скорости. Другими словами, для вашего вопроса, если фильтр Bloom сообщает вам, что элемент пока не был замечен, вы можете быть уверены, что этого не произошло. Но если он говорит, что элемент был замечен, вам действительно нужно проверить. Это по-прежнему экономит много времени, если в вашем списке не так много дубликатов (для тех, которые не выполняются, за исключением случая с небольшой вероятностью ложного позитива - вы обычно выбираете этот показатель в зависимости от того, насколько которое вы готовы предоставить фильтру Bloom (правило большого пальца: менее 10 бит на уникальный элемент для ложной положительной скорости 1%).

Существует множество реализаций фильтров Bloom, см., например, здесь или здесь, поэтому я не буду повторять что в этом ответе. Предположим, что api, описанный в этой последней ссылке, в частности, описание put(E e):

true, если биты фильтра Bloom изменились в результате этой операции. Если биты изменились, это, безусловно, первый раз, когда объект добавлен в фильтр. Если бит не изменился, это может быть первый случай, когда объект добавлен в фильтр. (...)

Реализация с использованием такого фильтра Блума будет следующей:

public static int[] removeDuplicates(int[] arr) {
    ArrayList<Integer> out = new ArrayList<>();
    int n = arr.length;
    BloomFilter<Integer> bf = new BloomFilter<>(...);  // decide how many bits and how many hash functions to use (compromise between space and false positive rate)

    for (int e : arr) {
        boolean might_contain = !bf.put(e);
        boolean found = false;
        if (might_contain) {
            // check if false positive
            for (int u : out) {
                if (u == e) {
                    found = true;
                    break;
                }
            }
        }
        if (!found) {
            out.add(e);
        }
    }
    return out.stream().mapToInt(i -> i).toArray();
}

Очевидно, что если вы можете изменить входящий массив на месте, тогда нет необходимости в ArrayList: в конце, когда вы знаете фактическое количество уникальных элементов, просто arraycopy() тех.

Ответ 23

Почему все люди не проверяют эти строки ниже?

Мне нужно написать свою собственную реализацию - не использовать Set, HashSet и т.д. Или любые другие инструменты, такие как итераторы. Просто массив для удаления дубликатов.

Я отправляю очень простую реализацию, заботясь над указанной строкой.

public class RemoveDuplicates {

public static void main(String[] args) {

    int[] arr = { 1, 2, 3, 4, 2, 3, 1 }; // input array
    int len = arr.length;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < len; j++) {
            if (arr[i] == arr[j]) {
                while (j < (len) - 1) {
                    arr[j] = arr[j - 1];
                    j++;
                }
                len--;
            }
        }
    }
    for (int i = 0; i < len; i++) {
        System.out.print("  " +arr[i]);
    }

   }
 }

Вход: 1, 2, 3, 4, 2, 3, 1

Выход: 1 2 3 4

Ответ 24

Вот мое решение. Сложность времени равна o (n ^ 2)

public String removeDuplicates(char[] arr) {
        StringBuilder sb = new StringBuilder();

        if (arr == null)
            return null;
        int len = arr.length;

        if (arr.length < 2)
            return sb.append(arr[0]).toString();

        for (int i = 0; i < len; i++) {

            for (int j = i + 1; j < len; j++) {
                if (arr[i] == arr[j]) {
                    arr[j] = 0;

                }
            }
            if (arr[i] != 0)
                sb.append(arr[i]);
        }

        return sb.toString().trim();
    }

Ответ 25

public void removeDup(){ 
String[] arr = {"1","1","2","3","3"};
          boolean exists = false;
          String[] arr2 = new String[arr.length];
          int count1 = 0;
          for(int loop=0;loop<arr.length;loop++)
            {
              String val = arr[loop];
              exists = false;
              for(int loop2=0;loop2<arr2.length;loop2++)
              {     
                  if(arr2[loop2]==null)break;
                  if(arr2[loop2]==val){
                        exists = true;
                }
              }
              if(!exists) {
                    arr2[count1] = val;
                    count1++;
              }
            }
}

Ответ 26

 package javaa;

public class UniqueElementinAnArray 
{

 public static void main(String[] args) 
 {
    int[] a = {10,10,10,10,10,100};
    int[] output = new int[a.length];
    int count = 0;
    int num = 0;

    //Iterate over an array
    for(int i=0; i<a.length; i++)
    {
        num=a[i];
        boolean flag = check(output,num);
        if(flag==false)
        {
            output[count]=num;
            ++count;
        }

    }

    //print the all the elements from an array except zero (0)
    for (int i : output) 
    {
        if(i!=0 )
            System.out.print(i+"  ");
    }

}

/***
 * If a next number from an array is already exists in unique array then return true else false
 * @param arr   Unique number array. Initially this array is an empty.
 * @param num   Number to be search in unique array. Whether it is duplicate or unique.
 * @return  true: If a number is already exists in an array else false 
 */
public static boolean check(int[] arr, int num)
{
    boolean flag = false;
    for(int i=0;i<arr.length; i++)
    {
        if(arr[i]==num)
        {
            flag = true;
            break;
        }
    }
    return flag;
}

}

Ответ 27

Это вопрос интервью: удаляйте дубликаты из массива. Я не должен использовать какие-либо наборы или коллекции. Полное решение:

public class Test4 {
public static void main(String[] args) {
     int a[] = {1, 2, 2, 3, 3, 3, 6,6,6,6,6,66,7,65}; 
              int newlength =    lengthofarraywithoutduplicates(a);
              for(int i = 0 ; i < newlength ;i++) {
                  System.out.println(a[i]);
              }//for
}//main

private static int lengthofarraywithoutduplicates(int[] a) {
     int count = 1 ;
     for (int i = 1; i < a.length; i++) {
          int ch = a[i];
          if(ch != a[i-1]) {
              a[count++] = ch;
          }//if
    }//for
    return count;

}//fix

}//end1

Ответ 28

public static int[] removeDuplicates(int[] arr) {

int end = arr.length;

 HashSet<Integer> set = new HashSet<Integer>(end);
    for(int i = 0 ; i < end ; i++){
        set.add(arr[i]);
    }
return set.toArray();
}

Ответ 29

Вот более простой и лучший способ сделать это, используя вместо этого arraylists:

public static final <T> ArrayList<T> removeDuplicates(ArrayList<T> in){
    ArrayList<T> out = new ArrayList<T>();
    for(T t : in) 
        if(!out.contains(t)) 
            out.add(t);
    return out;
}

Ответ 30

Если вам разрешено использовать потоки Java 8:

Arrays.stream(arr).distinct().toArray();