数组中没有重复项

本文关键字：数组 | 更新日期: 2023-09-27 18:26:16

 void RemoveDups(){
    int f=0;
    for(int i=1;i<nelems;i++){
        if(arr[f]==arr[i]){
            for(int k=i;k<nelems;k++)
            {
                arr[k]=arr[k+1];
            }
            nelems--;
        }
        if(i==(nelems+1)){
            f++;
           i=f+1; //increment again
        }
    }
}

这是我编写的从数组中删除重复元素的逻辑，但这根本不起作用 - 我应该进行哪些更改才能使其工作 - 或者考虑到时间复杂性，你们有更好的逻辑来做同样的事情，我不想使用内置方法来实现这一目标。

数组中没有重复项

int

end = input.length;

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

我认为您可以使用集合

将所有值复制到哈希集，然后使用迭代器访问值

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

您有两个选项，C# 具有 Distinct(( Linq 表达式，它将为您执行此操作(错过了 Java 标记(，但是如果您需要删除项目，您是否考虑过先对列表进行排序，然后将当前项目与上一项进行比较，如果它们相同，请删除它们。这意味着您的二重液检测只会在阵列中运行一次。

如果你担心排序，你可以很容易地实现一个有效的气泡排序或类似的东西

。

在你比较 examlpe arr[0] 到 arr[5] 之后，你永远不会减少i，你永远不会测试arr[1] == arr[2]

您需要在增加 f 后开始一个新的循环 (i(。

尝试

for(int f=0;f<nelems-1;f++)
{
  for(int i=f+1;i<nelems;i++)
  {
   ...
  }
}

使用此嵌套 for 循环，您可以比较数组的每个两个元素。

一个好的开始是在不缩小数组的情况下消除重复元素，最后完成： 

public class run2 extends Thread {
public static void main(String[] args) {
    int arr[] = { 1, 2, 2, 3, 5, 6, 5, 5, 6, 7 };
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] == -1)
                j++;
            if (arr[i] == arr[j])
                arr[j] = -1;
        }
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + ",");
    }
    System.out.println();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == -1) {
            for (int j = i; j < arr.length; j++) {
                if (arr[j] != -1) {
                    arr[i] = arr[j];
                    arr[j] = -1;
                    break;
                }
            }
        }
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + ",");
    }
}

}

改编此代码：

public static int[] removeDuplicates(int[] numbersWithDuplicates) {
        // Sorting array to bring duplicates together      
        Arrays.sort(numbersWithDuplicates);     
        int[] result = new int[numbersWithDuplicates.length];
        int previous = numbersWithDuplicates[0];
        result[0] = previous;
        for (int i = 1; i < numbersWithDuplicates.length; i++) {
            int ch = numbersWithDuplicates[i];
            if (previous != ch) {
                result[i] = ch;
            }
            previous = ch;
        }
        return result;
}

据我从您的代码中了解到，您正在比较从索引 0 开始的每个值到元素的其余部分，当您看到位于索引 f 处的元素时，您正在尝试移动整个数组并减小数组(nelems(的大小。看11号线 

if(i==(nelems+1)){
            f++;
            i=f+1;

问题是当 i 设置为 f+1 时，i 将在下一次迭代的 for 循环中再次递增。所以基本上我从 f+2 开始比较.而且你正在比较 i 和 (nelems+1( 考虑到 nelems 减少的情况，但你没有考虑当我到达终点而不减少 nelems 的情况在这种情况下，我永远不会等于 (nelems+1(。现在考虑你的逻辑，你可以做两件事。

1.这是您的工作代码。

for(int i=1;i<nelems;i++){
        if(arr[f]==arr[i]){
            for(int k=i+1;k<nelems;k++)
            {
                arr[k-1]=arr[k];
            }
            if(i==(nelems-1)){
                f++;
                i=f;
            }
            nelems--;   
        }
        if(i==(nelems-1)){//end of the loop
           f++;
           i=f; //increment again
    }
}

2.您也可以使用外部 for 循环，一旦内部 for 完成，它将增加 f 值。

void RemoveDups(){
    for(int f=0;f<nelems;++f){
        for(int i=1;i<nelems;i++){
            if(arr[f]==arr[i]){
                for(int k=i;k<nelems;k++)
                    arr[k]=arr[k+1];
                nelems--;
            }
         }
       }
    }

现在你的问题已经解决了，但你的代码的时间复杂度将是(O(N^3((。

现在，与其在第 4 行移动整个数组，不如将 arr[f] 与最后一个元素交换。

if(arr[f]==arr[i]){
        swap(arr[f],arr[nelems-1]);   
        nelems--;
  }

它将把时间复杂度从 O(N^3( 降低到 O(N^2(。

现在我会向你推荐我的方法

1.只需对数组进行排序。它将在O(NlogN(中完成。2.现在使用一个for循环，你可以得到你想要的。

void RemoveDups(){
        int k=0,i;
            for(i=1;i<nelems;++i){
             while(arr[i]==arr[i-1])
                 ++i;
             arr[k++]=arr[i-1];
           }
    arr[k++]=arr[i-1];
}

现在基本上你得到了一个大小为 k 的数组，它包含排序顺序的非重复元素，我的解决方案的时间复杂度为 O(NlogN(。

相关文章：