java 在数组中查找不重复的元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/27722009/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding non duplicate element in an array
提问by Leo
I am stuck in the following program:
我被困在以下程序中：
I have an input integer array which has only one non duplicate number, say {1,1,3,2,3}. The output should show the non duplicate element i.e. 2.
我有一个输入整数数组，它只有一个非重复数字，比如 {1,1,3,2,3}。输出应显示非重复元素，即 2。
So far I did the following:
到目前为止，我做了以下工作：
public class Solution {
public int singleNumber(int[] arr){
int size = arr.length;
int temp = 0;
int result = 0;
boolean flag = true;
int[] arr1 = new int[size];
for(int i=0;i<size;i++){
temp = arr[i];
for(int j=0;j<size;j++){
if(temp == arr[j]){
if(i != j)
//System.out.println("Match found for "+temp);
flag = false;
break;
}
}
}
return result;
}
public static void main(String[] args) {
int[] a = {1,1,3,2,3};
Solution sol = new Solution();
System.out.println("SINGLE NUMBER : "+sol.singleNumber(a));
}
}
Restricting the solution in array is preferable. Avoid using collections,maps.
最好将解决方案限制在数组中。避免使用集合、地图。
采纳答案by dasblinkenlight
Since this is almost certainly a learning exercise, and because you are very close to completing it right, here are the things that you need to change to make it work:
由于这几乎可以肯定是一项学习练习，并且因为您非常接近正确完成它，因此您需要更改以下内容才能使其正常工作：
- Move the declaration of
flaginsidethe outer loop- the flag needs to be set totrueevery iteration of the outer loop, and it is not used anywhere outside the outer loop. - Check the
flagwhen the inner loop completes- if theflagremainstrue, you have found a unique number; return it.
- 移动外循环
flag内部的声明- 需要将标志设置为true外循环的每次迭代，并且不在外循环外的任何地方使用。 - 检查
flag内循环完成的时间- 如果flag仍然存在true，则您已找到唯一编号；把它返还。
回答by user7258708
public class NonRepeatingElement {
public static void main(String[] args) {
int result =0;
int []arr={3,4,5,3,4,5,6};
for(int i:arr)
{
result ^=i;
}
System.out.println("Result is "+result);
}
}
回答by roshan posakya
/// for duplicate array
static void duplicateItem(int[] a){
/*
You can sort the array before you compare
*/
int temp =0;
for(int i=0; i<a.length;i++){
for(int j=0; j<a.length;j++){
if(a[i]<a[j]){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
int count=0;
for(int j=0;j<a.length;j++) {
for(int k =j+1;k<a.length;k++) {
if(a[j] == a[k]) {
count++;
}
}
if(count==1){
System.out.println(a[j]);
}
count = 0;
}
}
/*
for array of non duplicate elements in array just change int k=j+1; to int k = 0; in for loop
*/
static void NonDuplicateItem(int[] a){
/*
You can sort the array before you compare
*/
int temp =0;
for(int i=0; i<a.length;i++){
for(int j=0; j<a.length;j++){
if(a[i]<a[j]){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
int count=0;
for(int j=0;j<a.length;j++) {
for(int k =0 ;k<a.length;k++) {
if(a[j] == a[k]) {
count++;
}
}
if(count==1){
System.out.println(a[j]);
}
count = 0;
}
}
public class DuplicateItem {
public static void main (String []args){
int[] a = {1,1,1,2,2,3,6,5,3,6,7,8};
duplicateItem(a);
NonDuplicateItem(a);
}
回答by roshan posakya
/// for first non repeating element in array ///
static void FirstNonDuplicateItem(int[] a){
/*
You can sort the array before you compare
*/
int temp =0;
for(int i=0; i<a.length;i++){
for(int j=0; j<a.length;j++){
if(a[i]<a[j]){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
int count=0;
for(int j=0;j<a.length;j++) {
//int k;
for(int k =0; k<a.length;k++) {
if(a[j] == a[k]) {
count++;
}
}
if(count==1){
System.out.println(a[j]);
break;
}
count = 0;
}
}
public class NonDuplicateItem {
public static void main (String []args){
int[] a = {1,1,1,2,2,3,6,5,3,6,7,8};
FirstNonDuplicateItem(a);
}
回答by Pankaj Bhardwaj
From Above here is the none duplicated example in Apple swift 2.0
func noneDuplicated(){
let arr = [1,4,3,7,3]
let size = arr.count
var temp = 0
for i in 0..<size{
var flag = true
temp = arr[i]
for j in 0..<size{
if(temp == arr[j]){
if(i != j){
flag = false
break
}
}
}
if(flag == true){
print(temp + " ,")
}
}
}
// output : 1 , 4 ,7
// this will print each none duplicated
回答by Dileep
If you are coding for learning then you can solve it with still more efficiently.
如果您正在为学习而编码，那么您可以更有效地解决它。
- Sort the given array using merge sort of Quick Sort. Running time will be nlogn.
- The idea is to use Binary Search. Till required element found All elements have first occurrence at even index (0, 2, ..) and next occurrence at odd index (1, 3, …). After the required element have first occurrence at odd index and next occurrence at even index.
- 使用快速排序的合并排序对给定数组进行排序。运行时间将为 nlogn。
- 这个想法是使用二分搜索。直到找到所需元素 所有元素第一次出现在偶数索引 (0, 2, ..) 和下一次出现在奇数索引 (1, 3, ...)。在所需元素第一次出现在奇数索引后，下一次出现在偶数索引后。
Using above observation you can solve :
使用上述观察，您可以解决：
a) Find the middle index, say ‘mid'.
a) 找到中间的索引，比如“mid”。
b) If ‘mid' is even, then compare arr[mid] and arr[mid + 1]. If both are same, then the required element after ‘mid' else before mid.
b) 如果 'mid' 是偶数，则比较 arr[mid] 和 arr[mid + 1]。如果两者相同，则需要在 'mid' 之后的元素，否则在 mid 之前。
c) If ‘mid' is odd, then compare arr[mid] and arr[mid – 1]. If both are same, then the required element after ‘mid' else before mid.
c) 如果 'mid' 是奇数，则比较 arr[mid] 和 arr[mid – 1]。如果两者相同，则需要在 'mid' 之后的元素，否则在 mid 之前。
回答by Pratik Hublikar
Another simple way to do so..
另一种简单的方法来做到这一点..
public static void main(String[] art) {
int a[] = { 11, 2, 3, 1,1, 6, 2, 5, 8, 3, 2, 11, 8, 4, 6 ,5};
Arrays.sort(a);
System.out.println(Arrays.toString(a));
for (int j = 0; j < a.length; j++) {
if(j==0) {
if(a[j]!=a[j+1]) {
System.out.println("The unique number is :"+a[j]);
}
}else
if(j==a.length-1) {
if(a[j]!=a[j-1]) {
System.out.println("The unique number is :"+a[j]);
}
}else
if(a[j]!=a[j+1] && a[j]!=a[j-1]) {
System.out.println("The unique number is :"+a[j]);
}
}
}
Happy Coding..
快乐编码..
回答by Luca Rocchi
not tested but should work
未测试但应该可以工作
public class Solution {
public int singleNumber(int[] arr){
int size = arr.length;
int temp = 0;
int result = 0;
boolean flag = true;
int[] arr1 = new int[size];
for(int i=0;i<size;i++){
temp = arr[i];
int count=0;
for(int j=0;j<size;j++){
if(temp == arr[j]){
count++;
}
}
if (count==1){
result=temp;
break;
}
}
return result;
}
回答by Vedant Terkar
Try:
尝试：
public class Answer{
public static void main(String[] args) {
int[] a = {1,1,3,2,3};
int[] b =new int[a.length];
//instead of a.length initialize it to maximum element value in a; to avoid
//ArrayIndexOutOfBoundsException
for(int i=0;i<a.length;i++){
int x=a[i];
b[x]++;
}
for(int i=0;i<b.length;i++){
if(b[i]==1){
System.out.println(i); // outputs 2
break;
}
}
}
}
PS: I'm really new to javai usually code in C.
PS：我真的很陌生，java我通常用C.
回答by jgr208
I have a unique answer, it basically takes the current number that you have in the outer for loop for the array and times it by itself (basically the number to the power of 2). Then it goes through and every time it sees the number isn't equal to double itself test if its at the end of the array for the inner for loop, it is then a unique number, where as if it ever find a number equal to itself it then skips to the end of the inner for loop since we already know after one the number is not unique.
我有一个独特的答案，它基本上采用数组的外部 for 循环中的当前数字并对其进行计时（基本上是 2 的幂的数字）。然后它通过，每次看到数字不等于 double 本身测试它是否在内部 for 循环的数组末尾，然后它是一个唯一数字，就好像它曾经找到一个数字等于它本身然后跳到内部 for 循环的末尾，因为我们已经知道一个数字不是唯一的。
public class Solution {
public int singleNumber(int[] arr){
int size = arr.length;
int temp = 0;
int result = 0;
int temp2 = 0;
int temp3 = 0;
boolean flag = true;
int[] arr1 = new int[size];
for(int i=0;i<size;i++){
temp = arr[i];
temp2 = temp*temp;
for(int j=0;j<size;j++){
temp3 = temp*arr[j];
if(temp2==temp3 && i!=j)
j=arr.length
if(temp2 != temp3 && j==arr.length){
//System.out.println("Match found for "+temp);
flag = false;
result = temp;
break;
}
}
}
return result;
}
public static void main(String[] args) {
int[] a = {1,1,3,2,3};
Solution sol = new Solution();
System.out.println("SINGLE NUMBER : "+sol.singleNumber(a));
}
}
