Topic tags :- Array, Hash Table, Sorting
Question type :- Easy
Question link : Contains Duplicate
Note : Try yourself before seeing solution here.
Question :
Given an integer array nums, return true if any value appears
at least twice in the array, and return false if every
element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
Solutions : in Java
Solution 1:
import java.util.*;
class Solution {
public boolean containsDuplicate(int[] nums) {
Hashtable<String, Integer> numbers = new
Hashtable<>();
for(Integer i:nums){
if(numbers.get(Integer.toString(i))!=null){
return true;
}
numbers.put(Integer.toString(i),i);
}
return false;
}
}
Runtime: 21 ms
Memory Usage: 52.4 MB
Solution link : click here
Solution 2:
class Solution {
public boolean containsDuplicate(int[] nums) {
Hashtable<String, Integer> numbers = new
Hashtable<>();
for(Integer i:nums){
if(numbers.get(Integer.toString(i))!=null){
return true;
}
numbers.put(Integer.toString(i),i);
}
return false;
}
}
Runtime: 42 ms
Memory Usage: 52.6 MB
Solution link : click here
Solution 3:
class Solution {
public boolean containsDuplicate(int[] nums) {
int min = nums[0];
int max = nums[0];
for(int i=1;i<nums.length;i++) {
if(nums[i]<min) {
min = nums[i];
}
if(nums[i]>max) {
max = nums[i];
}
}
boolean[] checkArray = new boolean[max-min+1];
for(int i=0;i<nums.length;i++) {
if(checkArray[nums[i] - min]) {
return true;
}
checkArray[nums[i] - min] =
true;
}
return false;
}
}
Runtime: 4 ms
Memory Usage: 48.4 MB
Solution link : click here
Solution 4:
class Solution {
public boolean containsDuplicate(int[] nums) {
for(int i=0;i<nums.length;i++){
boolean swapped=false;
for(int
j=1;j<nums.length-i;j++){
if(nums[j]<nums[j-1]){
int
temp=nums[j];
nums[j]=nums[j-1];
nums[j-1]=temp;
swapped=true;
}
}
if(!swapped){
break;
}
}
//binary search
int start=0;
int end=nums.length-1;
if(nums.length==2){
if(nums[0]==nums[1]){
return true;
}return false;
}
while(start<end){
if(nums[start]==nums[start+1]){
return true;
}else{
start++;
}
if(nums[end]==nums[end-1]){
return true;
}else{
end--;
}
int mid=start+(end-start)/2;
if(nums[mid]==nums[mid+1]||nums[mid]==nums[mid-1]){
return true;
}
}
return false;
}
}
Runtime: 123 ms
Memory Usage: 42 MB
Solution link : click here
Thank you
0 Comments