This is the 21st day of my participation in the August More Text Challenge

Related articles

LeetCode brush questions summary: LeetCode brush questions

1. Title Description

A number that appears only once

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

Description:

Your algorithm should have linear time complexity. Can you do it without using extra space

Start with simple questions to brush, exercise their thinking ability, for the interview preparation ~

Second, train of thought analysis

  • Look at the examples in the title, let’s clarify the idea ~

  • Example 1:

    Input: [2,2,1] output: 1Copy the code

  • Example 2:

    Input: [4,1,2, 2] Output: 4Copy the code

  • The key of a hashMap is unique

  • We can put all of the values in the array into the map as keys, and of course the value is 1.

  • Loop through, and if it comes up again, we can add value+1.

  • The last value returned with a value of 1 is a value that occurs only once!

AC code

  • HashMap brute force:

    class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); // Add the value for(int I = 0; i < nums.length; i++){ if(map.containsKey(nums[i])){ map.put(nums[i], map.get(nums[i])+1); } else{ map.put(nums[i], 1); For (Integer key: map.keyset ()){if(map.get(key) == 1){return key; } } return 0; }}Copy the code
    • It’s definitely stupid!
    • But the main idea is that we can take full advantage of every feature in the Map to do this!

  • Quick sort crack:

    Class Solution {public int singleNumber(int[] nums) {// Array.sort (nums); // enumerate the even number of nums for(int I =0; i+1<nums.length; If (nums[I]! = 1) {if(nums[I]! = 1) {if(nums[I]! = 1) { =nums[i+1]) { return nums[i]; Return nums[nums.length-1]; return nums[nums.length-1]; }}Copy the code
    • Subject duplicate elements in front of you remember | LeetCode brush notes
    • Arrays. Sort (nums);
    • After sorting the proof, if the equality is worth it must be right and left adjacent!
    • We only need to determine the even digits, because at least once!
    • If all the preceding numbers appear twice, take it for granted!

Four,

  • Thousands of ideas to solve the problem, whether this method is good, or whimsical solution, can solve is a good way! White cat black cat can catch mice cat is a good cat!

  • Here are a few other LeetCode solutions for reference!

  • Click to jump: official solution

  • Click to jump: Xor algorithm

    • Xor solution is too awesome!! A look is highly recommended! You can expand your mind!

I see a long way to go, I’m sure I’ll keep searching ~ ** If you think I’m a good blogger! Writing is not easy, please like, follow, comment and give encouragement to the blogger ~ Hahah