My Java Solution using Merge Sort, any other sort solution?


  • 0
    S
    public class Solution {
        int[] location; //keep value where it used to be put
        public int[] twoSum(int[] numbers, int target) {
            //bottom up merge sort
            
            int[] result = new int[2];
            
            int [] sorted = merge_sort(numbers,0,numbers.length-1);
            for(int i = 0;i<numbers.length-1;i++){
                for(int j = i+1;j<numbers.length;j++)
                    if(sorted[i] + sorted[j] == target){
                        findResult(numbers,result,sorted[i],sorted[j]);
                        return result;
                    }else if(sorted[i] + sorted[j] >= target){
                        break;
                    }
            }
            return result;
        }
        private int[] merge_sort(int A[],int start, int end){
            int result [] = new int [end-start+1];
            if(start == end){
                result[0]=A[start];
                return result;
            }
            int A1[] =merge_sort(A,start,(start+end)/2);
            int A2[] = merge_sort(A,(start+end)/2+1,end);
            return merge(A1,A2);
        }
        
        private int[] merge(int[] A,int[]B){
            int []result = new int [A.length+B.length];
            int i = 0,j = 0;
            int num = 0;
            while(num<A.length+B.length){
                if(i<A.length && j< B.length){
                    if(A[i]<B[j]){
                        result[num] = A[i++];
                    }else{
                        result[num] = B[j++];
                    }
                }else if(j == B.length){
                    result[num] = A[i++];
                }else{
                    result[num] = B[j++];
                }
                num++;
            }
            return result;
            
        }
        private void findResult(int A[],int result[],int m,int n){
            int j = 0;
            for(int i = 0;i<A.length;i++){
                if(A[i] == m || A[i] == n)
                {
                    result[j ++] = i+1;
                }
            }
        }
       
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.