数组中重复的数字

数组中重复的数字

http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524

解法一:

  • 时间复杂度O(N),空间复杂度O(N)
import java.util.*;

public class Solution {
    public int duplicate (int[] a) {
        int[] b = new int[a.length]; // 辅助数组,其下标代表值,数值代表出现次数
        for (int i = 0; i < a.length; i++) {
            if (b[a[i]] == 0) b[a[i]]++;
            else return a[i];
        }
        return -1;
    }
}

解法二:

  • 《剑指Offer》官方答案,就地交换,每一个数字交换不会超过2次
  • 时间复杂度O(N),空间复杂度O(1)
import java.util.*;

public class Solution {
    public int duplicate (int[] a) {
        for (int i = 0; i < a.length; i++) {
            while (a[i] != i) {
                if (a[i] == a[a[i]]) return a[i];
                else {
                    int tmp = a[a[i]];
                    a[a[i]] = a[i];
                    a[i] = tmp; 
                }
            }
        }
        return -1;
    }
}
全部评论

相关推荐

牛牛不会牛泪:脉脉太多这种了,纯水军
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务