方法一: 使用数组记录数字是否出现过, 时间复杂度为 O(n), 空间复杂度为 O(n)
- public boolean duplicate(int numbers[],int length,int [] duplication) {// 数组 my
- if(null==numbers||length!=numbers.length){
- return false;
- }
- boolean[] num = new boolean[length];
- for(int i=0;i<length;i++){
- if(num[numbers[i]]){
- duplication[0]=numbers[i];
- return true;
- }
- else{
- num[numbers[i]]=true;
- }
- }
- return false;
- }
方法二: 修改原始数组 (不推荐), 访问过的数, 数组中对应位置值 - length, 时间复杂度为 O(n), 空间复杂度为 O(1)
- public boolean duplicate(int numbers[],int length,int [] duplication) {// 数组 mytip
- if(null==numbers||length!=numbers.length){
- return false;
- }
- for(int i=0;i<length;i++){
- int num = numbers[i];
- if(num<0){
- num += length;
- }
- if(numbers[num]<0){
- duplication[0]=num;
- return true;
- }
- else{
- numbers[num] -= length;
- }
- }
- return false;
- }
方法三: 使用 HashSet, 此方法通用,, 时间复杂度为 O(n), 空间复杂度为 O(n)
- public boolean duplicate(int numbers[],int length,int [] duplication) {//set my
- if(null==numbers||length!=numbers.length){
- return false;
- }
- Set<Integer> set = new HashSet<>();
- for(int i=0;i<length;i++){
- if(set.contains(numbers[i])){
- duplication[0]=numbers[i];
- return true;
- }
- else{
- set.add(numbers[i]);
- }
- }
- return false;
- }
来源: http://www.bubuko.com/infodetail-3016188.html