找到数组的第一个非重复整数

本文介绍了找到数组的第一个非重复整数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这个程序为所有非重复元素提供输出，但我首先需要一个非重复元素。我试图保持 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.