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

数组中重复的数字

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

参考:

    //解题思路
    /*替换法(O(n),O(1))
    数组存放原则:numbers[i] = i
    遍历数组所有元素,交换不符合数组存放原则的元素:
        例如[2,3,1,0,2]
        遍历0位元素2:(交换0位元素2和2位元素1)->[1,3,2,0,2]
        遍历0位元素1:(交换0位元素1和1位元素3)->[3,1,2,0,2]
        遍历0位元素3:(交换0位元素3和3位元素0)->[0,1,2,3,2]
        依次遍历0、1、2、3位置元素,都符合存放原则numbers[i] = i,不做任何操作
        遍历末位元素2,此时末位元素2和2位元素2相等,出现了两次,即数字2位重复元素
     */
    public int duplicate (int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != i){
                if (numbers[i] == numbers[numbers[i]]) return numbers[i];
                int temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = temp;
                i--;//遍历完0位元素以及交换完数字后,如果0位元素仍不符合数组存放原则:numbers[i] = i,那么还要重新遍历0位元素
            }
        }
        return -1;
    }

自己写的:

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        int[] count_numbers = new int[numbers.length];
        for(int i = 0; i < count_numbers.length; i++){
            count_numbers[i] = 0;
        }
        for(int i = 0; i < numbers.length; i++){
            count_numbers[numbers[i]] = count_numbers[numbers[i]] + 1;
            if (count_numbers[numbers[i]] == 2){
                return numbers[i];
            }
        }
        return -1;
    }
}
全部评论

相关推荐

07-22 11:07
门头沟学院 Java
点赞 评论 收藏
分享
熬夜冠军🏆:和你情况差不多,你这个HR算敞亮了,直白告诉你了,不浪费你时间,我的那个还跟我说没法说,只能等。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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