@[toc]

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

哈希表基础知识

代码随想录—哈希表理论基础

遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法

基本概念

哈希表（Hash table，也叫散列表），是根据关键字（key）直接进行访问的数据结构，它通过把关键值映射到表中一个位置（数组下标）来直接访问，以加快查找关键值的速度。这个映射函数叫做哈希（散列）函数，存放记录的数组叫做哈希（散列）表。

给定表（M），存在函数f（key），对任意的关键值key，代入函数后若能得到包含该关键字的表中地址，称表M为哈希表，函数f（key）为哈希函数。

• 最终会计算key的哈希值接着计算出数组索引位置。

最简单哈希：字符哈希

最简单的哈希：字符哈希，因为字符的个数有限，那么即可使用字符的ascii来作为数组的下标。

/**
 * @ClassName CharHash
 * @Author ChangLu
 * @Date 4/2/2022 10:07 AM
 * @Description 字符哈希：使用字符的ascii来作为哈希的下标
 */
public class CharHash {

    //题：对给定字符串中的字符进行统计
    public static void main(String[] args) {
        String str = "asdfsafdsdddfdsf";
        countAppearChat(str);
    }

    /**
     * 将字符串中的每个字符的ascii码作为统计数组的下标。由于字符数量有限可以直接使用其作为索引下标统计
     * @param str 
     */
    public static void countAppearChat(String str){
        int[] chs = new int[128];
        for (int i = 0; i < str.length(); i++) {
            chs[str.charAt(i)]++;
        }
        for (int i = 0; i < 128; i++) {
            if (chs[i] > 0){
                System.out.println(String.format("字符%c出现了%d次",(char)i,chs[i]));
            }
        }
    }

}

Hash表的实现（手写Map）

问题引入1：任意元素的映射（若是我们想让任何元素来进行映射，具备数组索引的效果，那么需要解决的是如何将key这种非num类型的转为对应的索引下标）

解决：利用哈希函数

思路：将关键值（大整数、字符串、浮点数等）转化为整数再对表长取余，从而关键字值被转换为哈希表的表长范围内的整数。

问题引入2：不同整数或字符串，由于哈希函数的选择，映射到同一个下标，发生冲突。（那么假设大数key的计算得到的哈希与原本计算得到的出现了重复，那么这种情况如何解决？）

解决：拉链法解决冲突

思路：①将所有哈希函数结果相同的结点连接在同一个单链表中。【数组+链表】②将对应连接的链表转为树来进行存储【数组+红黑树，JDK中1.8以上hashMap实现】

下面是①方式实现的存储、插入、搜索思路及代码：

//存储
存储：若选定的哈希表长度为m，则可将哈希表定义为一个长度为m的指针数组t[0…m-1]，指针数组中的每个指针指向哈希函数结果相同的单链表。【数组中存储的node结点可以是链表中的结点带有next指针，这种能够方便在出现哈希冲突时采用头插法或尾插法方式来插入到对应结点的前后】
//插入
插入：将value对应的结点key以头插法的方式插入到以t[hash_key]为头指针的单链表中
//搜索
搜索：遍历以t[hash_key]为头指针的单链表，查找链表各个结点的值域是否为value
    
//手写简易版的HashMap
/**
 * @ClassName DiyHashMap
 * @Author ChangLu
 * @Date 4/2/2022 10:34 AM
 * @Description 手写数组+链表：最最简单的一个HashMap实现
 */
class Node{
    private Object key;
    private Object value;
    private Node next;

    public Node(Object key,Object value) {
        this.key = key;
        this.value = value;
    }

    public Node(Object key,Object value, Node next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Object getKey() {
        return key;
    }

    public void setKey(Object key) {
        this.key = key;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Node node = (Node) o;

        if (key != null ? !key.equals(node.key) : node.key != null) return false;
        if (value != null ? !value.equals(node.value) : node.value != null) return false;
        return next != null ? next.equals(node.next) : node.next == null;
    }

    @Override
    public int hashCode() {
        int result = key != null ? key.hashCode() : 0;
        result = 31 * result + (value != null ? value.hashCode() : 0);
        result = 31 * result + (next != null ? next.hashCode() : 0);
        return result;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", value=" + value +
                ", next=" + next +
                '}';
    }
}

class MyMap{
    Node[] nodes;

    //构建Map的容量
    public MyMap(int capacity){
        if (capacity < 16) {
            nodes = new Node[capacity];
        }else {
            //计算出capacity最高幂
            nodes = new Node[Integer.highestOneBit(capacity)];
        }
    }

    //插入
    public void put(Object key,Object value){
        //1、计算key的hash值
        int hashKey =  key.hashCode() & (nodes.length - 1);
        //2、获取对应下标Node结点，看是否存在
        Node node = nodes[hashKey];
        //若是不存在直接插入
        if (node == null){
            nodes[hashKey] = new Node(key,value);
            return;
        }
        //若是存在，遍历Node结点(若是有结点，直接覆盖)
        Node cur = node;
        while (cur != null) {
            //判断key是否相同
            if (key.equals(cur.getKey())) {
                cur.setValue(value);
                return;
            }
            cur = cur.getNext();
        }
        //若是没有结点，采用头插法
        nodes[hashKey] = new Node(key,value,node);
    }

    //获取
    public Object get(Object key){
        //1、获取到对应的node结点
        int hashKey =  key.hashCode() & (nodes.length - 1);
        //2、遍历node来获取对应的值
        Node node = nodes[hashKey];
        Node cur = node;
        while (cur != null){
            //判断对应的node结点的key是否相同，若是相同那么直接返回
            if (cur.getKey().equals(key)){
                return cur.getValue();
            }
            cur = cur.getNext();
        }
        return null;
    }

}

public class DiyHashMap {

    public static void main(String[] args) {
        final MyMap myMap = new MyMap(20);
        myMap.put("changlu","123");
        myMap.put("changlu","456");
        System.out.println(myMap.get("changlu"));
        System.out.println(myMap.get("liner"));
    }

}

HashMap 基本使用

1、基本使用
（1） 插入键值对数据

public V put(K key, V value)

（2）根据键值获取键值对值数据

public V get(Object key)

（3）获取Map中键值对的个数

public int size()

（4）判断Map集合中是否包含键为key的键值对

public boolean containsKey(Object key)

（5）判断Map集合中是否包含值为value的键值对

boolean containsValue(Object value)

（6）判断Map集合中是否没有任何键值对

public boolean isEmpty()

（7）清空Map集合中所有的键值对

public void clear()

（8）根据键值删除Map中键值对

public V remove(Object key)

2、遍历
（1）将Map中所有的键装到Set集合中返回

//public Set keySet();
Set set=map. keySet()

（2）返回集合中所有的value的值的集合

// public Collection values();
Collection c=map.values()

（3）将每个键值对封装到一个个Entry对象中,再把所有Entry的对象封装到Set集合中返回

// public Set<Map.Entry<K,V>> entrtSet();
Set<Map.Entry<K,V>> entrys=map.entrySet()

HashMap<String,Integer> map =new HashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
map.put("d", 4);

//key封装成一个set集合即可进行遍历
final Iterator<String> iterator = map.keySet().iterator();

//将key、value封装到一个entry中，接着将多个entry放置到一个set里，最后使用迭代器方式来进行迭代遍历
final Iterator<Map.Entry<String, Integer>> mapIterator = map.entrySet().iterator();
while (mapIterator.hasNext()) {
    final Map.Entry<String, Integer> next = mapIterator.next();
    System.out.println(String.format("key:%s,value:%d",next.getKey(),next.getValue()));
}

---

剑指offer

剑指 Offer 03. 数组中重复的数字【简单】

参考文章：剑指 Offer 03. 数组中重复的数字（哈希表 / 原地交换，清晰图解）

题目链接：剑指 Offer 03. 数组中重复的数字

题目内容：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

解法：

1、暴力：nxn来进行比较。

复杂度分析：

• 时间复杂度：O(n^2^)
• 空间复杂度：O(1)

2、哈希表：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
    public int findRepeatNumber(int[] nums) {
        //采用哈希
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return nums[i];
            }else {
                map.put(nums[i], 1);
            }
        }
        return -1;
    }
}

3、原地交换法（最优解）：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

核心条件：题目给出的核心条件值为[0, n - 1]，值与索引对应。

class Solution {
    //原地解法
    //核心条件：nums中的数字值范围为[0, n - 1]
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i != nums.length) {
            int num = nums[i];
            if (num == i) {  //若是索引为本身不作操作
                i++;
            }else if (num == nums[num]) { //若是本身值与对应索引位置的值相同，说明重复
                return num;
            }else {
                //若是当前值与索引值不相等的话，那么就进行交换值（其实就是将自己这个索引值换到目标索引位置上，那么之后若是有出现相等的值找索引就能够快速找到了）
                //对于交换后i无需++，示例：3,4,2,1,1,0，一定要当前索引位置再进行检查一遍
                nums[i] = nums[num];
                nums[num] = num;  
            }
        }
        return -1;
    }
}

---

剑指 Offer 50. 第一个只出现一次的字符【简单】

题目链接：剑指 Offer 50. 第一个只出现一次的字符

题目内容：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

思路：

1、字典表，双层遍历【简单】

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {

    //第一个只出现一次的  s中只包含小写字母
    public char firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return ' ';
        }
        //26个字母
        int[] target = new int[26];
        for (int i = 0; i < s.length(); i++) {
            target[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (target[s.charAt(i) - 'a'] == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }
    
}

---

剑指 Offer 53 - I. 在排序数组中查找数字【简单】

题目链接：剑指 Offer 53 - I. 在排序数组中查找数字 I

题目内容：统计一个数字在排序数组中出现的次数。

思路：

1、二分+搜索。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    public int search(int[] nums, int target) {
        //1、定位数字的索引位置
        //123 45   12 34
        int left = 0, right = nums.length - 1;
        int mid = -1;
        boolean flag = false;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                flag = true;
                break;
            }else if (nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        int res = 0;
        if (flag) {
            //2、左右去进行搜索
            res++;
            int x = mid - 1;
            int y = mid + 1;
            while (x >= 0 && nums[x] == target) {
                x--;
                res++;
            }
            while (y < nums.length && nums[y] == target) {
                y++;
                res++;
            }
        }
        return res;
    }
}

---

剑指 Offer 57. 和为s的两个数字【简单】

题目链接：剑指 Offer 57. 和为s的两个数字

题目内容：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

思路：看到递增首先就应该想到二分

1、哈希表

复杂度分析：时间O(n)、空间O(n)

class Solution {

    //递增、两数之和
    //滑动窗口
    public int[] twoSum(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(target - nums[i])) {
                return new int[]{nums[i], target - nums[i]};
            }
            set.add(nums[i]);
        }
        return new int[]{};
    }
}

2、双指针【最优】

复杂度分析：时间(n)、空间O(1)

class Solution {

    //递增、两数之和
    //双指针写法
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        //定位到右边指针<=target的位置
        while (r >= 0 && nums[r] > target) {
            r--;
        }
        int[] res = new int[2];
        //进行双指针变换
        while (l < r) {
            int num = nums[l] + nums[r];
            if (num == target) {
                res[0] = nums[l];
                res[1] = nums[r];
                break;
            }else if (num < target) {
                l++;
            }else {
                r--;
            }
        }
        return res;
    }

}

---

剑指 Offer 61. 扑克牌中的顺子【简单】

题目链接：剑指 Offer 61. 扑克牌中的顺子

题目内容：从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

思路：小大王为0可表示任意数，这题解题思路就在于max-min是否小于5，5就是牌的数量，还有就是过程中有没有出现过相同的牌。

1、set+遍历【推荐】

复杂度分析：时间O(n)、空间O(n)。由于最大n就是14，那么我们可以将其都看作是O(1)

class Solution {

    //聚焦于最大值-最小值（中间判断是否有重复的数）
    //set判重+遍历
    public boolean isStraight(int[] nums) {
        int[] bucket = new int[14];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        //桶14个，来进行索引计数判断是否有重复的
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                bucket[nums[i]]++;
                if (bucket[nums[i]] > 1) {
                    return false;
                }
                min = Math.min(min, nums[i]);
                max = Math.max(max, nums[i]);
            }
        }
        return max - min < 5;
    }

}

2、排序+计数遍历

复杂度分析：时间O(n+logn*n)、空间O(1)

class Solution {

    //聚焦于最大值-最小值（中间判断是否有重复的数）
    //排序+计数
    public boolean isStraight(int[] nums) {
       Arrays.sort(nums);
       int joker = 0;
       for (int i = 0; i < nums.length; i++) {
           if (nums[i] == 0) {
                joker++;
           }else {
                //处理中间相同的情况
                if (i > 0 && nums[i] == nums[i - 1]) {
                    return false;
                }
           }
       }
       return nums[4] - nums[joker] < 5;
    }

}

---

剑指 Offer 56 - I. 数组中数字出现的次数【中等，等同牛客第3题】

题目链接：剑指 Offer 56 - I. 数组中数字出现的次数

题目内容：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

思路：

1、哈希

2、位运算

复杂度分析：时间复杂度O(n)、空间复杂度O(1)

class Solution {
    //位运算
    public int[] singleNumbers(int[] nums) {
        int num = nums[0];
        for (int i = 1; i < nums.length; i++) {
            num ^= nums[i];
        }
        int k = 1;
        //找到k & num > 0的情况
        while ((k & num) == 0) {
            k = k << 1;
        }
        int num1 = 0;
        int num2 = 0;
        //二次遍历，拆分成两个进行异或操作
        for (int i = 0; i < nums.length; i++) {
            if ((k & nums[i]) > 0) {
                num1 ^= nums[i];
            }else {
                num2 ^= nums[i];
            }
        }
        return new int[]{num1, num2};
    }
}

---

剑指 Offer 56 - II. 数组中数字出现的次数 II【中等】

学习资料：视频：LeetCode刷题力扣题解 | 剑指Offer56 - II. 数组中数字出现的次数 II | 画图算法思路讲解及C++代码实现、博客-数组中数字出现的次数Ⅱ

题目链接：剑指 Offer 56 - II. 数组中数字出现的次数 II

题目内容：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

思路：

1、哈希表

2、位运算。既然出现了三次，我们就将每个数字的所有位进行相加，每一位最终%3，然后计算这个二进制数最终得到的值就是只出现一次的数字。

复杂度分析：时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int singleNumber(int[] nums) {
        //int 32位
        int[] counts = new int[32];
        int k = 1;//进位
        //对nums数组中的每个元素的每一位来进行相加
        for (int num: nums) {
            for (int i = 0; i < 32; i++) {
                counts[i] += num & k;
                num = num >> 1;
            }
        }
        //对所有统计的数字来进行计算
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = res + (counts[i] % 3) * k;
            k = k << 1;
        }
        return res;
    }
}

---

剑指 Offer 35. 复杂链表的复制【中等】

学习视频：LeetCode刷题力扣｜剑指Offer 35. 复杂链表的复制（题解思路分析及Python3代码实现）介绍了原地法

题目链接：剑指 Offer 35. 复杂链表的复制

题目内容：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路：

1、哈希表：

复杂度分析：时间复杂度O(n)，实际上是2n，空间复杂度O(n)

class Solution {
    //本题的本质是：深拷贝
    //困难点：若是仅仅走一层遍历的话，对应的next、random指向的结点都不是新的结点
    public Node copyRandomList(Node head) {
        //使用map实现
        Map<Node, Node> map = new HashMap<>();
        //第一次遍历：将所有的结点都拷贝了一份
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        //第二次遍历：将所有的空白结点的next、random来指向map中对应的next、random，实际上就是我们的一个新节点
        for (Node cur = head; cur != null; cur = cur.next) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(head);
    }
}

2、原地修改【推荐，让空间复杂度优化为O(1)】

复杂度分析：时间复杂度O(n)，实际上是3n；空间复杂度O(1)

class Solution {
    //本题的本质是：深拷贝
    //困难点：若是仅仅走一层遍历的话，对应的next、random指向的结点都不是新的结点
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        //原地修改：1->2->3
        //第一遍遍历：每个结点指向相同值的新节点
        //1->1'->2->2'->3->3'->null
        for (Node cur = head; cur != null; cur = cur.next.next) {  //注意是两个next
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
        }
        //第二遍遍历：为所有的新节点random来进行赋值
        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;//同样这里next指向的是random相同值的新节点
            }
        }
        //第三遍遍历：分离旧新节点（原始的、新的都要进行分离）
        //1->2->3->null
        //1'->2'->3'->null
        Node newNode = head.next;
        for (Node node = head, temp = null; node != null && node.next !=null;) {
            temp = node.next;
            node.next = temp.next;
            node = temp;
        }
        return newNode;
    }
}

剑指 Offer II 004. 只出现一次的数字【中等】

题目链接：剑指 Offer II 004. 只出现一次的数字 ，类似题与该目录里的牛客3类似。

题目内容：给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

思路1：哈希表。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }
}

思路2：位运算

…待做

剑指 Offer II 070. 排序数组中只出现一次的数字【中等】

教程：[LeetCode 136]. 只出现一次的数字[位运算技巧系列]

题目链接：剑指 Offer II 070. 排序数组中只出现一次的数字

题目内容：给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

思路1：进行异或运算

异或表达式：

num ^ 0 = num
num ^ num = 0
num ^ (num1 ^ num1) = num
(num ^ num1) ^  num1 = num

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int ans = 0;
        for (int num: nums) {
            ans ^= num; 
        }
        return ans;
    }
}

牛客

两数之和【简单】

题目链接：两数之和

题目内容：给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

思路：通过使用一个map来作缓存，key为值，value为index。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

import java.util.*;

public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < numbers.length; i++) {
            int val = numbers[i];
            if (map.containsKey(target - val)) {
                return new int[]{map.get(target - val) + 1, i + 1};
            }
            map.put(val, i);
        }
        return new int[2];
    }
}

数组中出现次数超过一半的数字是【简单】

题目链接：数组中出现次数超过一半的数字

题目内容：给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

思路1：使用一个map来存储值与次数，如key为值，value为出现数量。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //定义一个map，key存放int，value存放出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (!map.containsKey(array[i])) {
                map.put(array[i], 1);
            }else {
                map.put(array[i], map.get(array[i]) + 1);
            }
            if (map.get(array[i]) > array.length/2) {
                return array[i];
            }
        }
        return -1;
    }
}

数组中只出现一次的两个数字【中等，重点】

题目链接：数组中只出现一次的两个数字

题目内容：一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

题目信息梳理：

1个长度为n的数字，除了两个数字只出现1次，其余数字都出现2次
要找到这两次只出现一次的数字，并且升序返回

思路1：采用哈希表。①遍历一遍所有数字，将其添加到哈希表中，哈希表key为num，value为计数。②遍历一遍数字，来取出value为1的所有数字。③最后来进行升序返回。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        //哈希表
        Map<Integer, Integer> map = new HashMap<>();
        for (int number: array) {
            if (map.containsKey(number)) {
                map.put(number, map.get(number) + 1);
            }else {
                map.put(number, 1);
            }
        }
        int[] res = new int[2];
        int num = 0;
        //遍历一遍map集合
        for (int number: array) {
            if (map.get(number) == 1) {
                res[num++] = number;
            }
        }
        if (res[0] > res[1]) {
            return new int[]{res[1], res[0]};
        }
        return res;
    }
}

思路2：位运算【进阶】。

位运算基础：题解学习

a ^ a = 0
a ^ (b ^ b) = a
(a ^ b) ^ b = a

本道题我入手思路是先通过看代码题解(牛客网配套101题解)然后反推学习的。
步骤思路：①初始res=0然后异或所有num值，得到一个k。②然后找到这个k为1的二进制情况(k<<1推)。②接着再次遍历一遍所有数，遍历过程中去判断&值时的结果为0、1情况，最终用两个变量来记录两个数字。
案例：
①3 ^ 4 = 111
3 011
4 100
  111  求得k为001，你可以找到规律就是011 & 001 = 1 > 0、100 & 001 = 0

此时 3 ^ 4 ^ 4 ^ 6 = 111 ^ 010 = 101，本质实际上就是3 ^ 6 = 011 ^ 110 = 101，由于两个数是进行异或操作，那么某位相等的时候就是0，不相等就是1，那么找到这个不相等的位置，101中第1个或第三个位置都可，找到位置有什么用？由于位置上是不同值才能够得到1，那么一旦我们能够找到该位置就能够将其进行分组（必定能够找到，因为两个值是不相等的）。
k=1开始，当101 & 1时（循环），结果为1，那么k的最终值为1

那么使用k这个值来去&两个值看看，必定一个是0或者1，由于其他都是成对的，a ^ a = 0,我们无需关心数量了

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    //位运算
    public int[] singleNumbers(int[] nums) {
        int num = nums[0];
        for (int i = 1; i < nums.length; i++) {
            num ^= nums[i];
        }
        int k = 1;
        //找到k & num > 0的情况
        while ((k & num) == 0) {
            k = k << 1;
        }
        int num1 = 0;
        int num2 = 0;
        //二次遍历，拆分成两个进行异或操作
        for (int i = 0; i < nums.length; i++) {
            if ((k & nums[i]) > 0) {
                num1 ^= nums[i];
            }else {
                num2 ^= nums[i];
            }
        }
        return new int[]{num1, num2};
    }
}

缺失的第一个正整数【中等】

题目链接：缺失的第一个正整数

题目内容：给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数

思路1：利用哈希表。key为值，value为1，首先遍历一遍存储到哈希表中，由于题目说找到缺失的第一个正整数，那么只需要设置一个res值初始为1，然后不断对其进行自增然后判断是否在map中存在即可找到第一个正整数。

复杂度分析：

• 时间复杂度：O(n)，2n，第一次是遍历n个数字，第二次是遍历最大的整数值。
• 空间复杂度：O(n)，存储n个哈希值。

class Solution {
    public int firstMissingPositive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < nums.length;i++) {
            map.put(nums[i], 1);
        }
        int res = 1;
        while (map.containsKey(res)) {
            res++;
        }
        return res;
    }
}

思路2：原地哈希法。①首先遍历第一遍，将所有负数取值为n+1。②遍历第二遍，将索引为|nums[i] - 1|数组索引设置为负数。③遍历第三遍，若是找到第一个为正数的，其索引也就是i+1即为第一个整数，否则即为n+1。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //第一次遍历，将所有得负数修改为length + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        //将索引为（对应值<n得值）设置为负数，那么最终再遍历一次时非负数得索引即为第一个正数
        for (int i = 0; i < n; i++) {
            if (Math.abs(nums[i]) <= n) {
                nums[Math.abs(nums[i]) - 1] = -1 * Math.abs(nums[Math.abs(nums[i]) - 1]);
            }
        }
        //最后遍历即可得到第一个正数
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}