从数组中删除重复 [英] Delete Duplicate from an Array

问题描述

我需要从一个数组中删除重复的条目，但不能使用任何新的数据结构和相同的阵列应该只返回不同的元素。例如，如果我的数组是 1,3,3,3,5,55,67,1 那么结果应该是 1,3， 5,55,67 。

我相信我已经解决了这个问题，但我需要它是否是一个好的算法，或者如果你认为我需要改变某些事情了。

 公共无效DeleteDuplicate（INT []数组）
{
    int类型l = 0;
    INT在newPosition = array.Length -1;
    的for（int i = 0; I＆LT; array.Length;我++）
    {
        对于（INT J = I + 1; J＆LT; array.Length-L; J ++）
        {
            如果（数组[我] ==阵列[J]。）
            {
                INT TEMP =阵列[J]。
                阵列[J] =阵列[在newPosition]
                数组[在newPosition] =气温;
                newPosition--;
                升++;
            }
        }
    }
    Array.Resize（参考阵列，array.Length  - 升）;
}
 

解决方案

在一般情况下，这个问题你是否有维护元素的相对顺序。例如，是否有可能返回{1,2}进行输入{2，1，2，1}

如果它被允许，那么最快解决方案将是：

• 排序输入数组
• 通过它运行一次比较A [1]与[I + 1]和消除为O重复（N）

总的复杂性是O（N * LOGN）比N ^ 2，你提出更好的。

如果您必须preserve的初始顺序，那么我不准备提出一个解决方案。

I need to delete duplicate entries from an array, but can't use any new data structures and the same array should return only distinct elements. For example, if my array is 1,3,3,3,5,55,67,1 then the result should be 1,3,5,55,67.

I believe I have solved the problem, but I need your opinion on whether it is a good algorithm or if I need to change something.

public void DeleteDuplicate(int[] array)
{
    int l = 0;
    int newPosition = array.Length -1;
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = i + 1; j < array.Length-l; j++)
        {
            if (array[i] == array[j])
            {
                int temp = array[j];
                array[j] = array[newPosition];
                array[newPosition] = temp;
                newPosition--;
                l++;
            }
        }
    }
    Array.Resize(ref array, array.Length - l);
}

解决方案

In general, the question whether you have to maintain the relative ordering of the elements. For example, whether it is possible to return {1, 2} for input {2, 1, 2, 1}.

If it is allowed, then the fastest solution will be:

• sort input array
• run once through it comparing a[i] with a[i+1] and removing duplicates in O(N)'

The total complexity would be O(N*logN), which is better than N^2 you proposed.

If you must preserve the initial ordering, then I am not ready to propose a solution.

这篇关于从数组中删除重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！