[LeetCode 136] Single Number

문제 바로가기

Description

---

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1

---

• Input: nums = [2,2,1]
• Output: 1

Example 2

---

• Input: nums = [4,1,2,1,2]
• Output: 4

Example 3

---

• Input: nums = [1]
• Output: 1

Constraints

---

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Each element in the array appears twice except for one element which appears only once.

Hint

---

Hint 1

  Think about the XOR (^) operator's property.
	

Code

---

내 제출

---

class Solution {
    public int singleNumber(int[] nums) {
        List<Integer> list = new ArrayList<>();

        for (int i : nums) {
            list.add(i);
        }

        Collections.sort(list);

        for (int i = 1; i < list.size(); i += 2) {
            if (!list.get(i - 1).equals(list.get(i))) {
                return list.get(i - 1);
            }
        }

        return list.get(list.size() - 1);
    }
}

Runtime	Memory
18 ms	45.7 MB

다른 풀이

---

 class Solution {
    static{
        Solution o = new Solution();
        for(int i = 0; i < 500; ++i){
            o.singleNumber(new int[]{1, 1, 2, 4, 5, 4, 5});
        }
    }

    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int e : nums){
            ans ^= e;
        }
        return ans;
    }
}

Reference

---