题解 | #数组中重复的数字#

第一想法是两层for循环

import java.util.*;


public class Solution {
    public int duplicate (int[] numbers) {
        

        if (numbers.length == 0) {
            return -1;
        }
        
        for (int i = 0; i < numbers.length; i++) {
            for(int j=i+1;j<numbers.length;j++){
                if (numbers[i] == numbers[j]) {
                    return numbers[j];
                }
            }
        }
        return -1;
    }
}

时间复杂度O(n^2)

排名第一的写法

新建一个boolean数组，长度和numbers一样。默认值都为false。

看else后的语句，b[numbers[i]] = true; 把numbers数组中的值作为b数组的下标，赋为true。

    public int duplicate (int[] numbers) {
      boolean[] b =  new boolean[numbers.length];
      for(int i=0;i<numbers.length;i++){
          if(b[numbers[i]]){
              return numbers[i];
          }else{
              b[numbers[i]] = true;
          }
      }
      return -1;
    }