0

contain duplicate

How should I optimize this code sample,getting. Tlc import java.util.*; class Solution { public boolean containsDuplicate(int[] nums) { //tlc int s =0; boolean ans=true; int e = nums.length-1; if (nums.length <= 0) { return false; } while(s<e){ if(nums[s]!=nums[e]){ ans =false; s++; e--; } } return ans; } }

2nd Mar 2022, 2:43 PM
vikram Rathod
9 Réponses
+ 1
Yes i got what are you saying... thanks 👍
2nd Mar 2022, 4:28 PM
vikram Rathod
+ 1
Mustafa A, vikram Rathod here is a way to reduce the number of comparisons to nlog(n). Only compare from i to the end of the list. The items before i have been compared already. int end = nums.length; for (int i = 0; i < end-1; i++) { for (int j = i+1; j < end; j++) { if (nums[i] == nums[j]) { return true; // end here } } } return false; // no duplicates
2nd Mar 2022, 11:49 PM
Brian
Brian - avatar
0
First of all. A method that doesn't use object attributes should be static. You don't want to be forced to create an instance to use it. If you find a duplicate, you don't want to continue. You should return immediately. Otherwise, I would improve the readability of the code. Like this: int end = nums.length; for (int i = 0; i < end; i++) { for (int j = 0; j < end; j++) { if (i != j) { // ignore same element if (nums[i] == nums[j]) { return true; // end here } } } } return false; // no duplicates
2nd Mar 2022, 3:47 PM
Mustafa A
Mustafa A - avatar
0
I think this could use the n^2 time complexity
2nd Mar 2022, 4:20 PM
vikram Rathod
0
Yeah. But time time complexity is about worst case. This could take anything from 2 (the first two are duplicates) to n^2 (last two are duplicates). You don't need to force it. If there is one duplicate, then the list contains duplicates.
2nd Mar 2022, 4:26 PM
Mustafa A
Mustafa A - avatar
0
But its still showing TLC
2nd Mar 2022, 4:29 PM
vikram Rathod
0
vikram Rathod Try starting j with 1 instead. Otherwise it will compare the first element with itself for no reason.
2nd Mar 2022, 4:33 PM
Mustafa A
Mustafa A - avatar
0
vikram Rathod if you need further reduction in complexity, consider using a hashMap. That would reduce it to 2n -- that is, 1n to test for the number being already in the map with the containsKey() method, and subsequently 1n to add it to the map with the put() method.
3rd Mar 2022, 12:15 AM
Brian
Brian - avatar
0
Brian Yeah. That's true. Good point.
3rd Mar 2022, 6:26 AM
Mustafa A
Mustafa A - avatar