singleNumber

singleNumber.java

package code_fight;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by Hoan Nguyen on 3/15/2017.
 */

/*
You are given an array of integers in which every element appears twice, except for one. Find the element that only appears one time. Your solution should have a linear runtime complexity (O(n)). Try to implement it without using extra memory.

Example

For nums = [2, 2, 1], the output should be
singleNumber(nums) = 1.

Input/Output

[time limit] 3000ms (java)
[input] array.integer nums

Constraints:
1 ≤ nums.length ≤ 104,
-109 ≤ nums[i] ≤ 109.

[output] integer
*/

public class singleNumber {
    static int singleNumber(int[] nums) {


        for (int i = 0; i <= nums.length - 1; i++) {
            boolean check = true;

            for (int j = i + 1; j <= nums.length - 1; j++) {
                if (nums[i] == (int) Math.pow(10, 9) + 1) {
                    break;
                }
                if (nums[i] == nums[j]) {
                    nums[i] = nums[j] = (int) Math.pow(10, 9) + 1;
                    check = false;
                    break;
                }
            }

            if (nums[i] != (int) Math.pow(10, 9) + 1 && check) {
                return nums[i];
            }
        }
        return nums[0];
    }

    // cach2:

    static int singleNumber3(int[] nums) {

        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[i + 1]) {
                if (nums[i + 1] != nums[i + 2]) {
                    return nums[i + 1];
                }
            }
        }
        return nums[0];
    }

    static int singleNumber2(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int n : nums) {
            if (numSet.contains(n)) {
                numSet.remove(n);
            } else {
                numSet.add(n);
            }
        }

        for (int n : numSet) {
            return n;
        }
        return -1;
    }


    public static void main(String[] args) {
//        int nums[] = {2, 3, 1, 1, 2};
//        int nums[] = {1, 3, 1, -1, 3};
        int nums[] = {123456789, 836133896, 65475264, 836133896, 746254373, 1000000000, 542627588, 1000000000, 444088605, 65475264, 746254373, 542627588, 444088605};
//        int nums[] = {2, 2, 1};
//        int nums[] = {-1, -1, -2};
        System.out.println(singleNumber(nums));
        System.out.println(singleNumber2(nums));
        System.out.println(singleNumber3(nums));
    }
}