找到数组的第一个非重复整数 [英] Find the first non repeating integers of array

问题描述

这个程序为所有非重复元素提供输出，但我首先需要一个非重复元素。我试图保持 if（flag == 1）在j循环结束后打破循环，然后我测试但它不适用于所有情况

This program is giving output for all non-repeated elements but I need first one non-repeated element. I tried to keep if(flag==1) to break loop after the end of j loop, then I tested but it is not working for all cases

import java.util.Scanner;
public class first
{
    public static void main(String[] args) 
    {
        int n, flag = 0;
        Scanner s = new Scanner(System.in);
        System.out.print("Enter no. of elements you want in array:");
        n = s.nextInt();
        int a[] = new int[n];
        System.out.println("Enter all the elements:");
        for(int i = 0; i < n; i++)
        {
            a[i] = s.nextInt();
        }
        System.out.print("Non repeated first element is :");
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i != j)
                {
                    if(a[i]!= a[j])
                    {
                        flag = 1;

                    }
                    else
                    {
                        flag = 0;
                        break;
                    }
                    if(flag == 1)
                    {
                     System.out.print(" ");   
                     System.out.println(a[i]);
                     break; 
                    }
                }
            }

        }

    }
}

推荐答案

您可以构建两个集合， singleSet 和 repeatedSet ，分别为出现过一次且不止一次的元素。可以通过对元素进行一次迭代来创建它们。然后，进行第二次迭代，查询哪个是非重复的第一个元素：

You can construct two sets, singleSet and repeatedSet, respectively for elements appeared once and more than once. They can be created by doing one iteration on elements. Then, you do an a second iteration, to query which is the first element non-repeated:

int[] elements = { 1, 1, 2, 3, 3, 4 };
Set<Integer> singleSet = new HashSet<>();
Set<Integer> repeatedSet = new HashSet<>();

for (int e : elements) {
    if (repeatedSet.contains(e)) {
        continue;
    }
    if (singleSet.contains(e)) {
        singleSet.remove(e);
        repeatedSet.add(e);
    } else {
        singleSet.add(e);
    }
}

for (int e : elements) {
    if (singleSet.contains(e)) {
        return e;
    }
}

此解决方案是 O （n）解决方案，它应该比嵌套循环更快，这是 O（n ^ 2）。

This solution is a O(n) solution, it should be faster than the nested-loop, which is O(n^2).

您还可以用 singleList替换 singeSet ，最后，返回 singleList 中的第一个元素，这避免了元素的第二次迭代。因此解决方案更快。

You can also replace the singeSet by a singleList, and at the end, return the first element in the singleList, which avoid the 2nd iteration on elements. Thus the solution is even faster.

这篇关于找到数组的第一个非重复整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！