2ms java solution without "really modify" the array


  • -1
    N

    First note of the problem goes like "must not modify the array". Well, technically, you can modify any element as you like, no restrictions.

    So , I think the meaning of this note is that the array must remain unchanged after the function returns.
    It doesn't matter if i modify it in the middle of the function.

    Actually, I did modify the array , but i am also able to restore the array. Here goes my solution.

    1. as we know, every element is a positive number , so we can make good use of the 'sign' bit

    2. every element is in range[1,n], and the size of array is n+1. So if num = nums[i], then we can set the sign bit of nums[num] as 1 indicating that num has one occurence. But if the sign bit of nums[num] is already set to 1, then, we can say that num has a duplicate in the array

    3. restore the array by setting the sign bit to 0

    Here is my implementation:

    public int findDuplicate(int[] nums) {
        int ret = 0;
        int num,idxNum;
        for(int i=0;i<nums.length;i++){
            num = nums[i]&0x7FFFFFFF;
            idxNum = nums[num];
            if( (idxNum&0x80000000)!=0 ){
                ret = num;
                break;
            }else{
                nums[num] = idxNum|0x80000000;
            }
        }
        //restore the array
        for(int i=0;i<nums.length;i++){
            nums[i] &= 0x7FFFFFFF;
        }
        return ret;
    }
    

    This might seems like a petty tricks, but it's a possible solution.


  • 0
    S

    Hi, the problem explicitly stated: "assume the array is read only", you're changing elements in the array. But nice idea! :)


Log in to reply
 

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