java - Efficient way to count unique pairs in int array -

java - Efficient way to count unique pairs in int array -

this first post, hope complies posting guidelines of site. first of generic community: reading months , learned lot :o)

premise: i'm first years pupil of it.

here's question: i'm looking efficient way count number of unique pairs (numbers appear twice) in given positive int array (that's know), e.g. if:

int[] arr = {1,4,7,1,5,7,4,1,5};

the number of unique pairs in arr 3 (4,5,7).

i have difficulties in... evaluating efficiency of proposals let's say.

here's first code did:

int numcouples( int[] v ) { int res = 0; int count = 0; (int = 0 ; < v.length; i++){ count = 0; (int j = 0; j < v.length; j++){ if (i != j && v[i] == v[j]){ count++; } } if (count == 1){ res++; } } homecoming res/2; }

this shoudn't cause checks whole given array many times number of elements in given array... right me if i'm wrong.

this sec code:

int numcouples( int[] v) { int n = 0; int res = 0; (int = 0; < v.length; i++){ if (v[i] > n){ n = v[i]; } } int[] = new int [n]; (int = 0; < v.length; i++){ a[v[i]-1]++; } (int = 0; < a.length; i++){ if (a[i] == 2){ res++; } } homecoming res; }

i guess should improve first 1 since checks 2 times given array , 1 time n array, when n max value of given array. may not if n quite big guess...

well, 2 questions:

am understanding how "measure" efficiency of code?

there's improve way count number of unique pairs in given array?

edit: damn i've posted , i'm swamped answers! thanks! i'll study each 1 care, time beingness don't involving hashmap: out of knowledge yet (hence 1 time again insight:o) )

well, here's reply your's 2 questions:

am understanding how "measure" efficiency of code?

there various ways measure efficiency of code. first of all, people distinguish between memory efficiency , time efficiency. usual way count these values know, how efficient building blocks of algorithm. have @ wiki.

for instance, sorting using quicksort need n*log(n) operations. iterating through array need n operations, n number of elements in input.

there's improve way count number of unique pairs in given array?

here's solution you. complixity of 1 be: o(n*log(n)+n), o(...) big o notation.

import java.util.arrays; public class ctest { public static void main(string[] args) { int[] = new int[] { 1, 4, 7, 1, 7, 4, 1, 5, 5, 8 }; system.out.println("res: " + uniquepairs(a)); } public static int uniquepairs(int[] a) { arrays.sort(a); // have: [1, 1, 1, 4, 4, 5, 5, 7, 7] int res = 0; int len = a.length; int = 0; while (i < len) { // take first number int num = a[i]; int c = 1; i++; // count duplicates while(i < len && a[i] == num) { c++; i++; } system.out.println("number: " + num + "\tcount: "+c); // if spotted number 2 times, increment result if (c == 2) { res++; } } homecoming res; } }

java arrays algorithm int