logo标签列表

数组去重

algorithmarraysdata-structures
35

我有一个未排序的数组，如何最好地删除所有重复的元素？

例如：

a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3]

因此，在进行该操作后，数组应该看起来像

 a[1,5,2,6,8,9,10,3,4,11]
2
这是作业吗？如果不是的话，很多语言（至少脚本语言）都内置了这个功能。Ruby：[1, 2, 3, 2, 3, 1].uniq - jtbandes
1
使用一个临时字典，在读取元素时将其插入，以便在字典中已存在时将其移除。 - pascal
@jtbandes 这不是作业..我只是想知道基本上适当的算法。@pascal 使用临时字典意味着使用额外的内存（存储）吗？ - mohit
是的，例如，请参考马修的回答。 - pascal
1
如果您是C++用户，则可以在C++ STL <algorithm>中使用unique()函数。 - Abhinav Shrivastava
你可以观看这个链接，了解同样的问题：http://stackoverflow.com/questions/24944844/removing-duplicates-inside-insertion-sort/26177449#26177449 - isxaker
14个回答
0

这是我用C++创建的代码段，试试看

#include <iostream>

using namespace std;

int main()
{
   cout << " Delete the duplicate" << endl; 

   int numberOfLoop = 10;
   int loopCount =0;
   int indexOfLargeNumber = 0;
   int largeValue = 0;
   int indexOutput = 1;

   //Array to hold the numbers
   int arrayInt[10] = {};
   int outputArray [10] = {};

   // Loop for reading the numbers from the user input
   while(loopCount < numberOfLoop){       
       cout << "Please enter one Integer number" << endl;
       cin  >> arrayInt[loopCount];
       loopCount = loopCount + 1;
   }



    outputArray[0] = arrayInt[0];
    int j;
    for (int i = 1; i < numberOfLoop; i++) {            
        j = 0;
        while ((outputArray[j] != arrayInt[i]) && j < indexOutput) {
            j++;
        }
        if(j == indexOutput){
           outputArray[indexOutput] = arrayInt[i];
           indexOutput++;
        }         
    }

   cout << "Printing the Non duplicate array"<< endl;

   //Reset the loop count
   loopCount =0;

   while(loopCount < numberOfLoop){ 
       if(outputArray[loopCount] != 0){
        cout <<  outputArray[loopCount] << endl;
    }     

       loopCount = loopCount + 1;
   }   
   return 0;
}
0
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class testing {
    public static void main(String[] args) {
        EligibleOffer efg = new EligibleOffer();
        efg.setCode("1234");
        efg.setName("hey");
        EligibleOffer efg1 = new EligibleOffer();
        efg1.setCode("1234");
        efg1.setName("hey1");
        EligibleOffer efg2 = new EligibleOffer();
        efg2.setCode("1235");
        efg2.setName("hey");
        EligibleOffer efg3 = new EligibleOffer();
        efg3.setCode("1235");
        efg3.setName("hey");
        EligibleOffer[] eligibleOffer = { efg, efg1,efg2 ,efg3};
        removeDupliacte(eligibleOffer);
    }

    public static EligibleOffer[] removeDupliacte(EligibleOffer[] array) {
        List list = Arrays.asList(array);
        List list1 = new ArrayList();
        int len = list.size();
        for (int i = 0; i <= len-1; i++) {
            boolean isDupliacte = false;
            EligibleOffer eOfr = (EligibleOffer) list.get(i);
            String value = eOfr.getCode().concat(eOfr.getName());
            if (list1.isEmpty()) {
                list1.add(list.get(i));
                continue;
            }
            int len1 = list1.size();
            for (int j = 0; j <= len1-1; j++) {
                EligibleOffer eOfr1 = (EligibleOffer) list1.get(j);
                String value1 = eOfr1.getCode().concat(eOfr1.getName());
                if (value.equals(value1)) {
                    isDupliacte = true;
                    break;
                }
                System.out.println(value+"\t"+value1);
            }
            if (!isDupliacte) {
                list1.add(eOfr);
            }
        }
        System.out.println(list1);
        EligibleOffer[] eligibleOffer = new EligibleOffer[list1.size()];
        list1.toArray(eligibleOffer);
        return eligibleOffer;
    }
}
0
0

我的解决方案(O(N))不使用额外的内存，但是数组必须被排序(我的类使用插入排序算法，但这并不重要):

  public class MyArray
        {
            //data arr
            private int[] _arr;
            //field length of my arr
            private int _leght;
            //counter of duplicate
            private int countOfDup = 0;
            //property length of my arr
            public int Length
            {
                get
                {
                    return _leght;
                }
            }

            //constructor
            public MyArray(int n)
            {
                _arr = new int[n];
                _leght = 0;
            }

            // put element into array
            public void Insert(int value)
            {
                _arr[_leght] = value;
                _leght++;
            }

            //Display array
            public void Display()
            {
                for (int i = 0; i < _leght; i++) Console.Out.Write(_arr[i] + " ");
            }

            //Insertion sort for sorting array
            public void InsertSort()
            {
                int t, j;
                for (int i = 1; i < _leght; i++)
                {
                    t = _arr[i];
                    for (j = i; j > 0; )
                    {
                        if (_arr[j - 1] >= t)
                        {
                            _arr[j] = _arr[j - 1];
                            j--;
                        }
                        else break;
                    }
                    _arr[j] = t;
                }
            }

            private void _markDuplicate()
            {
                //mark duplicate Int32.MinValue
                for (int i = 0; i < _leght - 1; i++)
                {
                    if (_arr[i] == _arr[i + 1])
                    {
                        countOfDup++;
                        _arr[i] = Int32.MinValue;
                    }
                }
            }

            //remove duplicates O(N) ~ O(2N) ~ O(N + N)
            public void RemoveDups()
            {
                _markDuplicate();
                if (countOfDup == 0) return; //no duplicate
                int temp = 0;

                for (int i = 0; i < _leght; i++)
                {
                    // if duplicate remember and continue
                    if (_arr[i] == Int32.MinValue) continue;
                    else //else need move 
                    {
                        if (temp != i) _arr[temp] = _arr[i];
                        temp++;
                    }
                }
                _leght -= countOfDup;
            }
        }

和主要

static void Main(string[] args)
{
     Random r = new Random(DateTime.Now.Millisecond);
     int i = 11;
     MyArray a = new MyArray(i);
     for (int j = 0; j < i; j++)
     {
        a.Insert(r.Next(i - 1));
     }

     a.Display();
     Console.Out.WriteLine();
     a.InsertSort();
     a.Display();
     Console.Out.WriteLine();
     a.RemoveDups();
     a.Display();

    Console.ReadKey();
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接