Algorithms to Check if Array Contains Duplicate Elements

  • 时间：2020-09-12 10:06:27
  • 分类：网络文摘
  • 阅读：98 次

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true
Example 2:

Input: [1,2,3,4]
Output: false
Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Bruteforce Algorithm to Check If Array Contains Duplicates

The bruteforce algorithm: We can iterate over all pairs of numbers, then compare for equality. This takes O(N^2) quadric time, at the cost of a constant space.

Python:

1
2
3
4
5
6
7

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(0, i):
                if nums[i] == nums[j]:
                    return True
        return False
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(0, i):
                if nums[i] == nums[j]:
                    return True
        return False

Java:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 1; i < nums.length; ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
} 
class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 1; i < nums.length; ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
};
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
};

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    for (let i = 0; i < nums.length; ++ i) {
        for (let j = 0; j < i; ++ j) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
};
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    for (let i = 0; i < nums.length; ++ i) {
        for (let j = 0; j < i; ++ j) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
};

Check If Array Contains Duplicate After Sorting

If we sort the array (which will require O(N LogN)), then we can do a linear scan to check the two consecutive elements to find out if there are duplicates. The overall time complexity is improved to O(N LogN) and we are still using the O(1) constant space.

Python:

1
2
3
4
5
6
7

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

Java:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; ++ i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
} 
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; ++ i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

C++:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(begin(nums), end(nums));
        for (int i = 1; i < nums.size(); ++ i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
};
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(begin(nums), end(nums));
        for (int i = 1; i < nums.size(); ++ i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
};

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for (let i = 1; i < nums.length; ++ i) {
        if (nums[i] == nums[i - 1]) {
            return true;
        }
    }
    return false;
};
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for (let i = 1; i < nums.length; ++ i) {
        if (nums[i] == nums[i - 1]) {
            return true;
        }
    }
    return false;
};

Use Hash Set to Check the Duplicates

Further optimisation can be done via using a Hash Set. The complexity will be O(N) as we only need to conduct a linear scan. However, the space requirement is O(N) as we are using a Hash Set that complexity grows linear with the data set.

Python:

1
2
3
4
5
6
7
8

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        data = set()
        for i in nums:
            if i in data:
                return True
            data.add(i)
        return False
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        data = set()
        for i in nums:
            if i in data:
                return True
            data.add(i)
        return False

Java:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (Integer x: nums) {
            if (set.contains(x)) {
                return true;
            }
            set.add(x);
        }
        return false;
    }
}
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (Integer x: nums) {
            if (set.contains(x)) {
                return true;
            }
            set.add(x);
        }
        return false;
    }
}

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> cache;
        for (int i = 0; i < nums.size(); i ++) {
            if (cache.count(nums[i])) {
                return true;
            }
            cache.insert(nums[i]);
        }
        return false;
    }
};
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> cache;
        for (int i = 0; i < nums.size(); i ++) {
            if (cache.count(nums[i])) {
                return true;
            }
            cache.insert(nums[i]);
        }
        return false;
    }
};

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let data = new Set();
    for (let x of nums) {
        if (data.has(x)) {
            return true;
        }
        data.add(x);
    }
    return false;
};
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let data = new Set();
    for (let x of nums) {
        if (data.has(x)) {
            return true;
        }
        data.add(x);
    }
    return false;
};

This problem is the foundamental (basics) for Computer Science Interviews. In this post, we have listed 3 solutions that are implemented in four languages: C++, Java, Python and Javascript.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
炎炎夏日如何制作生津止渴的酸梅汤　 细数一根香蕉的12大神奇养生功效　 职场男性食补方略及饮食注意事项　 三款肉制食品诱惑红超标北京已下架　 保健食品虚假广告花样百出太坑人　 冰淇淋为何要加如此多的食品添加剂　 肉禽类的这些部位千万不要去吃　 百事可乐配方含致癌色素仍坚称安全　 调查称槟榔是一级致癌物可引发口腔癌　 嚼食槟榔对身体健康的危害非常大　
评论列表
添加评论