<pre>뭐 답 요청하는게 아니라요...
이 밑에 보면 메소드가 3개 있습니다..
처음꺼는 어레이 안에 있는 정수들중 중복되는걸 찾는것
두번째는 순서대로 숫자가 있는 어레이에서 빠진것 찾기
세번째는 중복된거 찾기인데...
이걸 런타임, 스페이스 최대한 효율적으로 해서 만들어야 되는건데...

저는 처음꺼는 해쉬테이블 두번째 세번째는 그냥 어레이 하나 더 만들어서 인덱스 사용했습니다..
런타임은 다 O(n)이고 스페이스도 O(n) 인데 제가 과연 효율적으로 코딩했나해서요..
시간 되시는 분들 피드백좀 주시면 감사하겠습니다.^^

        /*
         * It is known that more than half the numbers
         * in input array a are equal. The function
         * must find and return this number.
         * Examples:
         * a=[5,8,3,8,8] gives 8
         * a=[2172,1,2172,2172] gives 2172
         * a=[10,11,10,11,10,7,10] gives 10
         * a=[1,2,1,2] will never occur
         * The function is not allowed to modify a.
         */
        public int findMajority(int[] A) {
                Integer number, occurence;
                Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
                for(int i = 0; i < A.length; i++)
                {
                        if(hash.get(A[i]) == null)
                                hash.put(A[i], new Integer(1));
                        else
                                hash.put(A[i], new Integer(((Integer)hash.get(A[i])).intValue()+1));
                }
                Set<Integer> set = hash.keySet();
                Iterator<Integer> itr = set.iterator();
                number = itr.next();
                occurence = hash.get(number);
                while (itr.hasNext()) {
                        if(hash.get(itr.next()) > occurence)
                        {
                                number = itr.next();
                                occurence = hash.get(number);
                        }
                }
                if (number != null)
                        return number;
                return 0;
                ///////////////////////////////////////////////////////////////
                // run-time : O(n)
                // space : O(number of unique integers)
                ///////////////////////////////////////////////////////////////
        }
        
        /*
         * It is known that the input array a contains
         * all the numbers from 0 to a.length (including both endpoints),
         * except that one number is missing.
         * Find and return this number.
         * Examples:
         * a=[0,1,3,4] gives 2
         * a=[3,0,4,1] gives 2
         * a=[0,1,2] gives 3
         * a=[15,2] will never occur
         * a=[1,1] will never occur
         */
        public int findMissingLink(int[] a) {
                boolean [] arr = new boolean[a.length+1];
                for(int i = 0; i< a.length; i++)
                {
                        arr[a[i]] = true;
                }
                for(int j = 0; j < arr.length; j++)
                {
                        if(!arr[j])
                                return j;
                }
                return 0;
                ///////////////////////////////////////////////////////////////
                // run-time : O(n)
                // space : O(n)
                ///////////////////////////////////////////////////////////////
        }


        /*
         * It is known that the input vector a contains
         * only numbers between 1 and a.length-1 (both ends inclusive).
         * Find a number that occurs at least twice.
         * Examples:
         * A=[1,1,2,3] gives 1
         * A=[2,2,3,4,3] gives 2 or 3, either one is acceptable
         * A=[3,3,3,1] gives 3
         * A=[0,1,2,3] will not occur
         * The function is not allowed to modify A.
         */
        public int findTwins(int[] a) {
                int arr[] = new int[a.length];
                for(int i = 0; i < a.length; i++)
                {
                        arr[a[i]]++;
                }
                for(int j = 0; j < arr.length; j++)
                {
                        if(arr[j] >= 2)
                                return j;
                }
                return 0;
                ///////////////////////////////////////////////////////////////
                // run-time : O(n)
                // space : O(n)
                ///////////////////////////////////////////////////////////////
        }
</pre>