Non Built-In Java Solution with insertion sort


  • 0
    Q

    With HashMap or HashSet the problem is trivial, but the performance analysis with these built-in functions are always some kind of vague to me.

    Anyway, I use insertion sort to solve this problem by searching the insertion index for element (i + 1) within the element range from 0 to i. If the element of the insertion index is equal to the element with index (i + 1), then a duplicate is found.

    public class Solution {
        public boolean containsDuplicate(int[] nums) {
            if (nums == null) {
    			return false;
    		}
    		for (int i = 0; i < nums.length - 1; i++) {
    			if (insertOrder(nums, i)) {
    				return true;
    			}
    		}
    		return false;
    	}
    	
    	private boolean insertOrder(int[] nums, int endIndex) {
    	    int insertionIndex = getInsertIndex(nums, 0, endIndex, nums[endIndex + 1]);
    		if (nums[insertionIndex] == nums[endIndex + 1] && (insertionIndex != endIndex + 1)) {
    			return true;
    		} else {
    			int currentValue = nums[endIndex + 1];
    			for (int i = endIndex + 1; i >= insertionIndex + 1; i--) {
    				nums[i] = nums[i - 1];
    			}
    			nums[insertionIndex] = currentValue;
    		}
    		return false;
    	}
    	
    	private int getInsertIndex(int[] nums, int leftIndex, int rightIndex, int target) {
    		int m = leftIndex + (rightIndex - leftIndex) / 2;
    		
    		if (leftIndex > rightIndex) {
    			return leftIndex;
    		}
    		
    		if (target < nums[m]) {
    			return getInsertIndex(nums, leftIndex, m - 1, target);
    		} else if (target > nums[m]) {
    			return getInsertIndex(nums, m + 1, rightIndex, target);
    		} else {
    			return m;
    		}
    	}
    }

Log in to reply
 

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