Commitf162e92

authored

Create 1512-number-of-good-pairs.java

1 parent324f0e3 commitf162e92Copy full SHA for f162e92

File tree

+56

-0

lines changed

+56

-0

lines changed

Lines changed: 56 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,56 @@`
	`1`	`+/* Brute Force (Method 1)`
	`2`	`+-----------------------------`
	`3`	`+ Time Complexity: O(n^2)`
	`4`	`+ Space Complexity: O(1)`
	`5`	`+----------------------------*/`
	`6`	`+classSolution {`
	`7`	`+publicintnumIdenticalPairs(int[]nums) {`
	`8`	`+inti=0,j=0,c=0;`
	`9`	`+for(i=0;i<nums.length;i++){`
	`10`	`+for(j=i+1;j<nums.length;j++){`
	`11`	`+if(nums[i]==nums[j])`
	`12`	`+c++;;`
	`13`	`+ }`
	`14`	`+ }`
	`15`	`+returnc;`
	`16`	`+ }`
	`17`	`+}`
	`18`	`+`
	`19`	`+/* Combinations (Method 2)`
	`20`	`+---------------------------------`
	`21`	`+ Time Complexity: O(n)`
	`22`	`+ Space Complexity: O(n)`
	`23`	`+---------------------------------*/`
	`24`	`+classSolution {`
	`25`	`+publicintnumIdenticalPairs(int[]nums) {`
	`26`	`+Map<Integer,Integer>freq =newHashMap<>();`
	`27`	`+for(intn:nums)`
	`28`	`+freq.put(n,freq.getOrDefault(n,0) +1);`
	`29`	`+intres =0;`
	`30`	`+for(intc :freq.values()){`
	`31`	`+res +=c(c-1)/2;// Combination formula nC2 = nn(n-1)/2`
	`32`	`+ }`
	`33`	`+returnres;`
	`34`	`+ }`
	`35`	`+}`
	`36`	`+`
	`37`	`+/* Method 3`
	`38`	`+----------------------------`
	`39`	`+ Time Complexity: O(n)`
	`40`	`+ Space Complexity: O(n)`
	`41`	`+---------------------------*/`
	`42`	`+classSolution {`
	`43`	`+publicintnumIdenticalPairs(int[]nums) {`
	`44`	`+intres =0;`
	`45`	`+Map<Integer,Integer>freq =newHashMap<>();`
	`46`	`+for(intn :nums){`
	`47`	`+if(freq.containsKey(n)){`
	`48`	`+res +=freq.get(n);`
	`49`	`+freq.put(n,freq.get(n)+1);`
	`50`	`+ }`
	`51`	`+else`
	`52`	`+freq.put(n,1);`
	`53`	`+ }`
	`54`	`+returnres;`
	`55`	`+ }`
	`56`	`+}`

Comments

(0)