Linear but uses extra spaces..Accepted but needs improvement..Welcome Suggestions


  • 11
    D

    Below is my code. I used a set to record a new element and add it to the sum; if the element shows up again, delete it from the set and subtract it from the sum. At the end, the sum will be the single element.
    Thanks for comments and suggestions.

    public class Solution {
      public static int singleNumber(int[] A) {
        int single = 0;
        Set<Integer> s = new TreeSet<Integer>();
        for (int i : A) {
          if (s.contains(i)) {
            single = single - i;
            s.remove(i);
          } else {
            s.add(i);
            single = single + i;
          }
        }
      return single;
      }
    }

  • 31
    M

    There is a function that cancels out itself when run a second time on the first's result. It's called xor, or exclusive or. You can replace the set with an int, and just xor each element into the int, with each doubled int cancelling themselves out, leaving the single number alone at the end.

    int single=0;
    for(int i:A) single^=i;
    return single;

Log in to reply
 

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