This is the first day of my participation in the August Text Challenge.More challenges in August

Topic describes

Given an array of integers, determine whether there are duplicate elements. The function returns true if there is a value that appears in the array at least twice. Return false if each element in the array is different. Example 1: input, output,2,3,1 [1] : true example 2: input: [1, 2, 3, 4] output: false example 3: input, output,1,1,3,3,4,3,2,4,2 [1] : trueCopy the code

Ideas & CODE

1. Violent solution

The first thing that came to mind was the double for loop. Knowing that the time complexity was O(n^2), the simplest method worked best, so I submitted the following code

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

Unexpectedly timed out, it seems that the performance of letcode server is not very good, I ran the crash

2. The sorting

A double for loop that compares each value in the array and returns true if there is a repeat. Is there an easier way to do this? I took a peek at the solution and realized that someone had already done this: sort the array first and then compare adjacent elements

public boolean containsDuplicate2(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true; }}return false;
}
Copy the code

Beyond 99.7% of users!

3. Use the Set collection

When you see a repeating element, of course you have to think of a Set in Java, which is an unordered and unrepeatable Set. In that case, you can use sets to judge.

There are two ways:

  1. Insert all elements into Set, because Set is automatically de-duplicated. Compare the length of Set and array
  2. The Set ofadd()Method, which returns false if repeated elements are inserted, making things simple
public boolean containsDuplicate3(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int i : nums) {
        if(! set.add(i)) {return true; }}return false;
}
Copy the code

4. Lambda expressions, one line of code done!

In addition, the above ideas can also be implemented with lambda

public boolean containsDuplicate5(int[] nums) {
    returnIntStream.of(nums).distinct().count() ! = nums.length; }Copy the code

However, this method is also a traversal in nature, with time complexity of O(n) and low efficiency