java 从数组中删除重复项（无集合或排序）

Removing duplicates from an array (without sets or sorting)

提问by Kootling

I have the following code:

我有以下代码：

import java.util.Scanner;
public class ArrayDuplicates {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.print("How many numbers are you going to enter? ");
        int num = scan.nextInt();
        int[] arr = new int[num]; // initialize array with user inputted length
        for (int i = 0; i < arr.length; i++) { // enter numbers into array
            arr[i] = scan.nextInt();
        }

        int[] unique = new int[arr.length];    //initialize new array that will hold unique values
        for (int i = 0; i < arr.length; i++) {
            boolean b = true;    //boolean that checks if an element is a duplicate
            for (int j = i+1; j < arr.length; j++) {    //check all elements above int i
                if (arr[i] == arr[j]) {
                    b = false;    // set b to false if there is an existing duplicate
                }
            }
            if (b) {
                unique[i] = arr[i];    // if no duplicates exist, then it is unique.
            }
        }   
        for (int i = 0; i < unique.length; i++) {
                System.out.println(unique[i]);
        }
    }
}

The problem with this code (aside from being horribly slow for large arrays, but that's not the point) is that since the undeclared elements for the uniquearray will be set to 0, the duplicate elements from the first array are being set to 0in unique[](if that makes any sense). I understand why this happens, but cannot find an efficient way to fix this. I tried setting the duplicate elements to Integer.MIN_VALUEin the unique array and then printing only the elements of unique[]which are not equal to Integer.MIN_VALUE, but that seems like a weak solution to the problem. How can I fix this problem?

这段代码的问题（除了对于大数组来说非常慢，但这不是重点）是因为unique数组的未声明元素将被设置为0，第一个数组中的重复元素被设置为0in unique[]（如果有任何意义）。我理解为什么会发生这种情况，但找不到解决此问题的有效方法。我尝试将重复元素设置为Integer.MIN_VALUE唯一数组中，然后仅打印unique[]不等于的元素Integer.MIN_VALUE，但这似乎是解决问题的弱方法。我该如何解决这个问题？

EDIT:If I run the code:

编辑：如果我运行代码：

How many numbers are you going to enter? 4
1
2
2
0

你要输入多少个数字？4
1
2
2
0

Output:

输出：

1
0
2
0

Since the second element of the array is a duplicate, I do not set unique[1]to any value, making it default to 0. How do I avoid printing that 0, since it is not part of the original array?

由于数组的第二个元素是重复的，我没有设置unique[1]任何值，使其默认为 0。如何避免打印 0，因为它不是原始数组的一部分？

EDIT 2:Yes, this is homework, but the reason I don't want to use sets, sorting, etc. is primarily that I am not familiar with them. Also, as I am not asking anyone to write the entire program for me, I think it's fine to ask for a little help.

编辑 2：是的，这是作业，但我不想使用集合、排序等的原因主要是我不熟悉它们。另外，因为我没有要求任何人为我编写整个程序，所以我认为寻求一点帮助是可以的。

采纳答案by DreadHeadedDeveloper

I am going to use the tools that you used to solve the problem, cuz something in me is telling me this is homework...

我将使用你用来解决问题的工具，因为我内心的某些东西告诉我这是作业......

import java.util.Scanner;

public class ArrayDuplicates 
{

   public static void main(String[] args) 
   {

      Scanner scan = new Scanner(System.in);

      System.out.print("How many numbers are you going to enter? ");
      int num = scan.nextInt();

      int[] arr = new int[num]; // initialize array with user inputted length

      for (int i = 0; i < arr.length; i++)// enter numbers into array
      {

         arr[i] = scan.nextInt();

      }

      double[] unique = new double[arr.length];    //initialize new array that will hold unique values

      ///////My edit

      for(int z = 0; z < unique.length; z++)
      {

         unique[z] = -0.5;

      }

      ///////

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

         boolean b = true;    //boolean that checks if an element is a duplicate

         for (int j = i+1; j < arr.length; j++)    //check all elements above int i
         {

            if (arr[i] == arr[j]) 
            {

               b = false;    // set b to false if there is an existing duplicate

            }

         }

         if (b) 
         {

            unique[i] = arr[i];    // if no duplicates exist, then it is unique.

         }

      }   

      for (int i = 0; i < unique.length; i++) 
      {

         if(!(unique[i] == -0.5))
         {

            System.out.println((int)(unique[i]));

         }

      }

   }
}

So, you see where I commented out my edit? that's the new thing, a very easy way to check is to give the values a number that is notexpected, in this case, a negative number. Now, that is an assumption on my part, change -1 to whatever value you know will notbe entered into that Scanner. Same for the if statement.

所以，你看到我在哪里注释掉我的编辑了吗？这是新事物，一种非常简单的检查方法是为值提供一个非预期的数字，在本例中为负数。现在，这是我的假设，将 -1 更改为您知道不会输入到 that 中的任何值Scanner。if 语句也是如此。

回答by Stephen C

Any value that you choose (zero, min-int, max-int) to represent a removed duplicate is a problem. The user could always enter that number, and your program wouldn't behave correctly. (The only way you could legitimately use (say) min-int or max-int would be if the requirements clearly said that that number was invalid input.)

您选择的任何值（零、最小整数、最大整数）来表示已删除的重复项都是有问题的。用户总是可以输入该数字，而您的程序将无法正常运行。（您可以合法使用（例如） min-int 或 max-int 的唯一方法是，如果要求明确指出该数字是无效输入。）

The correct way to deal with duplicates is to keep a counter of the number of non-duplicates, and make sure that the duplicates (or slots that would contain them) are at the high end of the array; i.e. indexes >= the counter. (That becomes an invariant that your algorithm needs to maintain ...)

处理重复的正确方法是保留非重复数量的计数器，并确保重复（或包含它们的插槽）位于数组的高端；即索引 >= 计数器。（这成为您的算法需要维护的不变量......）

The best solution is to eliminate the duplicates before you add them to the array. Keep a count of the number of non-duplicates and iterate until that reaches your num... rather than the length of the array.

最好的解决方案是在将它们添加到数组之前消除重复项。计算非重复项的数量并进行迭代，直到达到您的num... 而不是数组的长度。

But if you do want to add all values to the array and theneliminate the duplicates, when you find a duplicate you need to swap elements so that you can maintain the invariant. The logic is a little bit fiddly ... but quite doable.

但是，如果您确实想将所有值添加到数组中，然后消除重复项，则当您发现重复项时，您需要交换元素，以便您可以保持不变。逻辑有点繁琐……但完全可行。

UPDATE

更新

I just noticed that your original solution was using two arrays. I assumed that you were using one array, and doing an in-place update to eliminate the duplicates.

我只是注意到您的原始解决方案使用了两个数组。我假设您正在使用一个数组，并进行就地更新以消除重复项。

回答by FunctionR

The best way to do this is to use a Map.

最好的方法是使用Map。

public interface Map<K,V>

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

将键映射到值的对象。地图不能包含重复的键；每个键最多可以映射到一个值。

I don't know why you would not want to use a set unless you are doing homework...

我不知道为什么除非你在做功课，否则你不想使用一套......

---

---

If you really can't use a set. Go ahead and create an ArrayList. Store the elements of the arrayinside, but everytime you want to store you check if the element is already part of the ArrayList.

如果你真的不能使用 set。继续创建一个ArrayList. 存储array内部的元素，但每次要存储时都要检查该元素是否已经是ArrayList.

 int [] list = {5, 5, 3, 2, 5, 3, 5};

 ArrayList<Integer> list2 = new ArrayList<Integer>();

 for(int i = 0; i < list.length; i++)
    if(!list2.contains(list[i]))
        list2.add(list[i]);

You can, if you want, turn your ArrayListback into an array.

如果你愿意，你可以把你的ArrayList背变成一个数组。

Object[] list3 = list2.toArray();

回答by ms2r

You can store the maximum value entered by user (while the user is entering the values in the first loop) and then make the default value for unique equals to max + 1.

您可以存储用户输入的最大值（当用户在第一个循环中输入值时），然后将 unique 的默认值设为 max + 1。

Or you can try another approach for solving the problem, something like this:

或者您可以尝试另一种方法来解决问题，如下所示：

  int num = scan.nextInt();
  int[] arr = new int[num];
  int[] uniq = new int[num+1000000];
  int j = 0;

  // enter numbers into array
  for (int i = 0; i < arr.length; i++) { 
     int input = scan.nextInt(); 
     if(uniq[input] != 1){
         uniq[input] = 1;  
         arr[j] = input;
         j++;
      }
   } 

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

Note that this solution is under the assumption that the user will not enter a number greater than (num + 1,000,000).

请注意，此解决方案假设用户不会输入大于 的数字(num + 1,000,000)。

回答by SkyMaster

This solution allows you to enter any integer value even negative. It's your same code with some modifications and has added a parallel array for comparisons. It has also removed some lines of code that are no longer needed.

此解决方案允许您输入任何整数值，甚至是负数。这是经过一些修改的相同代码，并添加了一个用于比较的并行数组。它还删除了一些不再需要的代码行。

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    System.out.print("How many numbers are you going to enter? ");
    int num = scan.nextInt();
    int[] arr = new int[num]; // initialize array with user inputted length
    int[] arrflag = new int[num];
    for (int i = 0; i < arr.length; i++) { // enter numbers into array
        System.out.print("Enter number: ");
        arr[i] = scan.nextInt();
        arrflag[i] = 0;
    }

    int[] unique = new int[arr.length];    //initialize new array that will hold unique values
    int n=0;
    for (int i = 0; i < arr.length; i++) {            
        if (arrflag[i] == 0) {
            unique[n++] = arr[i];
            for (int j = i+1; j < arr.length; j++) {    //check all elements above int i
                if (arr[i] == arr[j]) {                        
                    arrflag[j]=-1;
                }
            }                
        }
    }   
    for (int i = 0; i < n; i++) {
            System.out.println(unique[i]);
    }
}

回答by Guest

Create a parallel character array with all the values as '.' Whenever you find a duplicate, set the value to a ',' in the character array. Then Print only the values of your array that have a corresponding '.' in the character array.

创建一个并行字符数组，所有值都为 '.' 每当您找到重复项时，将值设置为字符数组中的“,”。然后只打印具有相应“.”的数组值 在字符数组中。

 }
    System.out.println();
    for (int i = 0; i < arr.length; i++) {
        if(a[i]=='.')
            System.out.println(arr[i]);
    }
}

}

}

回答by mike_dz

Example with String [].

字符串 [] 的示例。

public static List<String> arrListWithNoDups(String arr[]){

    Map<String, Integer>map = new HashMap<String, Integer>();
    List<String>list = new ArrayList<String>();

    for(int i = 0; i<arr.length; i++){
        if(map.get(arr[i]) == null){
            map.put(arr[i], 0);
        }
        else{
            map.put(arr[i], map.get(arr[i])+1);
        }
    }

    for(int j = 0; j<arr.length; j++){
        if(map.get(arr[j])==0){
            list.add(arr[j]);
        }
    }

    return list;

}

回答by BinDev

public class RemoveDuplicateFromArray {

公共类 RemoveDuplicateFromArray {

public static void main(String[] args) {

    int[] myArray = {1, 2, 1, 4, 1, 5, 2, 5};
    System.out.println("Before removing duplicate" + Arrays.toString(myArray));

    RemoveDuplicateFromArray rd = new RemoveDuplicateFromArray();
    int[] newArray = rd.findDuplicate(myArray);
    System.out.println("Before removing duplicate" + Arrays.toString(newArray));
}

public int[] findDuplicate(int[] inputArray) {
    Arrays.sort(inputArray);
    int count = 0;
    for (int i = 0; i < inputArray.length; i++) {
        if (i + 1 < inputArray.length && inputArray[i] == inputArray[i + 1]) {
            count++;
        }
    }
    int[] result = new int[inputArray.length - count];
    int c = 0;
    for (int j = 0; j < inputArray.length; j++) {
        if (j + 1 < inputArray.length && inputArray[j] == inputArray[j + 1]) {

        } else {
            result[c] = inputArray[j];
            c++;
        }
    }
    inputArray = result;
    return inputArray;
}

}

}

回答by Indra G

I tried to improved this code, please comments/suggest if further improvement can be done.

我试图改进此代码，请评论/建议是否可以进一步改进。

public static int[] removeDuplicate(int[] arr) {
    int[] noDuplicates = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        boolean b = true;

        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]){
                b = false;
            }
        }

        if (b) {
            noDuplicates[i] = arr[i];
            System.out.print(noDuplicates[i] + " ");
        }
    }
    return noDuplicates;

}

}

回答by kamlesh

void myFunction(int arr[])
{

    int size=arr.length;
    for(int i=0;i<size;i++)
    {
        for(int j=i+1;j<size;j++)
        {

            if(arr[i]==arr[j])
            {
                arr[j]=arr[size-1];
                size--;
            }
        }
    }

    for(int a=0;a<size;a++)
    {
        System.out.print(arr[a]+" ");
    }

}