Simple JAVA solution w/o using extra memory

  • -4
    public class Solution {
    public int singleNumber(int[] A) {
        if (A.length<=3) return 1;
        //suppose that special number is at A[0]
        int extra=A[0];
        //if A[1] is different than A[0]
        //it means A[0] is the special number
        if (A[1] !=extra){
                return extra;
        //if the A[1] is the same as A[0]
        // then the special number is in somewhere else
        for (int i=2;i<A.length; i++){
            if (A[i]==extra){
            //find a new number as potential special number
            //if the number after the new number is different,
            //means that new number is the special number
            if (i+1==A.length || A[i+1] !=extra){
                return extra;
        return -1;


  • 8

    I think the code does not use extra memory, but the time is not linear, since sorting the array is not linear.

  • 0

    The sorting is at least O(nlogn), so it's not linear.

Log in to reply

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