java - Set を使用せずに配列から重複を効率的に削除する方法

Question

配列内の重複した値を削除する独自の実装を作成するように依頼されました。これが私が作成したものです。しかし、1,000,000 個の要素をテストした後、完了するまでに非常に長い時間がかかりました。アルゴリズムやバグを改善するためにできることはありますか?

などを使用Setしないで、独自の実装を作成する必要があります。または、HashSetイテレータなどの他のツール。重複を削除するための単なる配列。

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];
                }
                end--;
                j--;
            }
        }
    }

    int[] whitelist = new int[end];
    for(int i = 0; i < end; i++){
        whitelist[i] = arr[i];
    }
    return whitelist;
}

Answer 1

Setコレクションの助けを借りることができます

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());
}

Answer 2

最も内側の for ループを削除することにより、元のコード自体をわずかに変更します。

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;
}

Answer 3

範囲は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) で実行されます。注意: 返された配列はソートされているため、それが不正な場合、この回答は無効です。

Answer 4

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

Answer 5

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

試しに上記のコードを書きました。ありがとう。

Answer 6

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^3) 時間ではなく、O(N) 時間で実行されます

Answer 7

これは、配列内の要素を並べ替える簡単な方法です

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]);
        }


    }
}

Answer 8

並べ替えられた配列の場合は、次のインデックスを確認してください。

//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;
}

Answer 9

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);
}

Answer 10

補助配列 (一時) を使用できます。これは、インデックスで主配列の数値です。したがって、時間の複雑さはライナーと O(n) になります。ライブラリを使用せずに実行したいので、別の配列 (一意) を定義して、重複しない要素をプッシュします。

var num = [2,4,9,4,1,2,24,12,4];
let temp = [];
let unique = [];
let j = 0;
for (let i = 0; i < num.length; i++){
  if (temp[num[i]] !== 1){
    temp[num[i]] = 1;
    unique[j++] = num[i];
  }
}
console.log(unique);

Answer 11

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;
    }

Answer 12

これが私の解決策です。時間計算量は 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();
    }

Answer 13

これは、Set、Map、List、または追加のコレクションを使用しておらず、2 つの配列のみを使用しています。

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

Answer 14

最初の答えは、Android Killerの答えが指摘したように、重複を削除するように設計されたハッシュセットを使用することです

アプローチ2:- しかし、setの使用が許可されていない場合は、最初にnlognになるクイックソートでソートしてから、XOR操作を適用して重複を見つけます

最適化されたもの

public static void removeDuplicates(int[] arr) {
        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-1; i++) {

            if((input[i]^input[i+1])==0){
                System.out.println(input[i]);
            }
        }

    }

Answer 15

サンプルを12個の要素として使用しましたが、

public class Remdup_arr {

public static void main(String[] args) {

    int a[] = {1,1,2,3,4,4,5,6,7,8,6,8};
    for(int p : a)
    {
        System.out.print(p);
        System.out.print("\t");
    }

    System.out.println();
    System.out.println();

    remdup(a);

}

private static void remdup(int[] a) {

    int length = a.length;
    int b[] = new int[11];
    int d = 1;
    b[0]=a[0];
    while(length<13 && length>0)
    {
        int x = a[length-1];
        if(!(contain(b , x)))
            {b[d] = a[length-1];
            d++;}
        length--;


    }

    for( int z = 0;z<b.length;z++){
        System.out.print(b[z]);
        System.out.print("\t");}

}

private static boolean contain(int[] b ,int p) {

    boolean bool = false;
    int len = b.length;
    for(int i = 0;i<len;i++)
    {
        if(p == b[i])
            bool = true;
    }



    return bool;

}

}

出力は次のとおりです:- 1 1 2 3 4 4 5 6 7 8 6 8

1 8 6 7 5 4 3 2 0 0 0

Answer 16

//Remove duplicate from sorted array

public class RemDupFromArray {
    static int num;
    public static void main(String[] args){
        int arr[] = {0,0,2,2,3, 5, 5,7, 7, 7};
        for(int i=0;i<arr.length-1;i++){
            if(num!=arr[i]){
                num=arr[i];
                System.out.print(arr[i]);
            }
        }
    }
}

Answer 17

public class RemoveDuplicates {
public Integer[] returnUniqueNumbers(Integer[] original,
        Integer[] uniqueNumbers) {
    int k = 0;  

    for (int j =  original.length - 1; j >= 0; j--) {
        boolean present = false;
        for (Integer u : uniqueNumbers) {
            if (u != null){
            if(u.equals(original[j])) {
                present = true;
            }}
        }
        if (present == false) {
            uniqueNumbers[k] = original[j];
            k++;
        }
    }
    return uniqueNumbers;
}

public static void main(String args[]) {
    RemoveDuplicates removeDup = new RemoveDuplicates();
    Integer[] original = { 10, 20, 40, 30, 50, 40, 30, 20, 10, 50, 50, 50,20,30,10,40 };
    Integer[] finalValue = new Integer[original.length + 1];

    // method to return unique values
    Integer[] unique = removeDup.returnUniqueNumbers(original, finalValue);

    // iterate to return unique values
    for (Integer u : unique) {
        if (u != null) {
            System.out.println("unique value : " + u);
        }
    }
}}

このコードは、同じ値の複数の重複を含むソートされていない配列を処理し、一意の要素を返します。

Answer 18

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

        int j = 0;
        int i = 1;
        //return if the array length is less than 2
        if(input.length < 2){
            return input;
        }
        while(i < input.length){
            if(input[i] == input[j]){
                i++;
            }else{
                j = j+1;
                input[j] = input[i];
                i = i+1;
            }    
        }
        int[] output = new int[j+1];
        for(int k=0; k<output.length; k++){
            output[k] = input[k];
        }

        return output;
    }

public static void main(String a[]){
        int[] input1 = {2,3,6,6,8,9,10,10,10,12,12};
        int[] output = removeDuplicates(input1);
        for(int i:output){
            System.out.println(i+" ");
        }
    }

Answer 19

import java.util.*;
class removeDuplicate{
int [] y ;

public removeDuplicate(int[] array){
    y=array;


    for(int b=0;b<y.length;b++){
        int temp = y[b];
        for(int v=0;v<y.length;v++){
            if( b!=v && temp==y[v]){
                y[v]=0;
            }
        }
    }




}

Answer 20

public class RemoveDuplicates {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int size;
        System.out.println("Enter an array size");
        Scanner sc=new Scanner(System.in);
        size = sc.nextInt();

        int arr[] = new int[size];

        System.out.println("Enter "+size+" numbers");
        for(int i=0;i<size;i++){
            arr[i]=sc.nextInt();
        }

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

                    int shiftLeft = j;

                    for (int k = j+1; k < size; k++, shiftLeft++) {
                        arr[shiftLeft] = arr[k];
                    }
                    size--;
                    j--;
                }
            }
        }
        System.out.println("New Array");
        for(int i=0;i<size;i++)
        {
            System.out.println(arr[i]);
        }
    }

}

Answer 21

それが役に立てば幸い...

if (!checked)//Condition to add into array {
        $scope.selectWeekDays.push(WeekKeys);
    } else {
        for (i = 0; i <= $scope.selectWeekDays.length; i++) // Loop to check IsExists {
            if ($scope.selectWeekDays[i] == WeekKeys)//then if Equals removing by splice {
                $scope.selectWeekDays.splice(i, 1);
                break;
            }
        }
    }