数组

一、知识

数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。

二、应用

1. 三数之和

排序+双指针

• 排序，排序让数组有序可以通过双指针来查找符合要求的元素，不排序则只能选取一个元素，再从剩下的元素中再选取一个，再去找最后一个元素，这样时间复杂度太高会超时
• 双指针，排好序后选定一个元素，使用双指针只要遍历一次数组即可查找出符合要求的其余两个元素，n个元素遍历n次，时间复杂度为O(n^2^)。

public List<List<Integer>> threeSum(int[] nums) {
    //排序
    Arrays.sort(nums);
    int length = nums.length;
    List<List<Integer>> list = new ArrayList<>();
    //选定元素
    for (int i = 0; i < length; i++) {
        //当该元素大于0则结束
        if (nums[i] > 0) {
            break;
        }
        //防止重复选定相同数值的元素
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        //双指针
        int j = i + 1, k = length - 1;
        while (j < k) {
            int sum = nums[j] + nums[k];
            if (sum > -nums[i]) {
                k--;
            } else if (sum < -nums[i]) {
                j++;
            } else {
                //所有元素符合要求，则加入集合
                list.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                j++;
                k--;
                //防止重复选定相同数值的元素
                while (j < k && nums[j] == nums[j - 1]) {
                    j++;
                }
                while (j < k && nums[k] == nums[k + 1]) {
                    k--;
                }
            }
        }
    }
    return list;
}

2. 多数元素

1. 哈希表
   • 将元素以及元素的个数存入哈希表中再次遍历哈希表找出元素个数大于n/2的元素

public int majorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int num = 0;
    for (int i : nums) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }
    int pass = nums.length / 2;
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() > pass) {
            num = entry.getKey();
        }
    }
    return num;
}

2. 摩尔投票法

public int majorityElement(int[] nums) {
    int cur = nums[0];
    int num = 1;
    for (int i : nums) {
        if (i == cur) {
            num++;
        } else if (--num == 0) {
            cur = i;
            num = 1;
        }
    }
    return cur;
}

3. 缺失的第一个正数

置换

• 题意要求找出为出现的最小整数，出现在1 ~ n范围的整数符合要求，我们可以利用原数组将在1 ~ n范围中的数 a 移动到数组下标为 a-1的位置（移动前需要判断原位置是否存在符合要求的值，防止死循环）,当所有元素换完后遍历数组，当前元素不为下标+1时，则该位置的数为缺失的第一个正数，遍历完成未发现则为 n+1

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //置换
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        //查看当前的数是否符合要求
        for (int i = 0; i < n; i++) {
            if ((i + 1) != nums[i]) {
                //不符合直接返回
                return i + 1;
            }
        }
        //未找到则为n+1
        return n + 1;
    }
}