战胜LeetCode刷题 【数组篇】

累计 - 1 - 题

136. 只出现一次的数字169. 多数元素15. 三数之和4. 寻找两个正序数组的中位数

前往题源
2022-01-11

题解：

方法一：使用辅助数组进行标记；（时间 N，空间 N）
方法二：使用快排将整个数组排序，单个的元素前后都不一样，可找出；(时间 N*logN，空间 1)
方法三：使用HashMap统计每个元素出现的个数；（时间 N ，空间 N）

class Solution {
    public int singleNumber(int[] nums) {
        Map map = new HashMap<>();
        // 1. 统计个数
        for (Integer i : nums) {
            Integer count = map.get(i);
            count = (count == null ? 1 : ++count);
            map.put(i, count);
        }
        // 2. 找出出现一次的元素
        for (Integer i : map.keySet()) {
            Integer count = map.get(i);
            if (count == 1) {
                return i;
            }
        }
        return -1; // can't find it.
    }
}

方法四：位运算（异或）；（时间 N ，空间 N）

异或运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b,将所有数字按照顺序做抑或运算，最后剩下的结果即为唯一的数字

因为异或运算的顺序没有影响，所有出现两次的元素可以相互异或为0，最后留下来的就是结果了，这个方法是真的6

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i : nums){
            ans ^= i; // 异或运算
        }
        return ans;
    }
}

前往题源
2022-01-11

方法一：使用HashMap统计每个元素出现的次数；
方法二：摩尔投票法；

由于最多的元素超过了一半，所有可以看做做多的元素是一类，其他元素为一类，在遍历过程中，记录下目前票数最多的（规则：不和自己相同的都视为反对票）

class Solution {
    public int majorityElement(int[] nums) {
    	// 1. 先记首元素为最高票
        int count = 1;
        int ans = nums[0];
        // 2. 遍历
        for(int i=1;i 
 
15. 三数之和 
前往题源
 2022-01-12
 
 
这个题目最容易想到的方法就是直接三重循环，那么时间复杂度为N*3，这就超时了。
 
自己刚开始在写的时候，加了挺多的条件进行剪枝操作，但是结果还是超时。
 
只有将时间复杂度降下一个维度，可以发现a,b,c当其中两个确定后，c也就唯一了，利用这个性质，将a,b选取固定后，c从后向前遍历寻找结果（这就使得b,c的遍历相当于只遍历一遍数组），最后总的时间复杂度为N*2。
 
class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> ans;
        int n = nums.size();
        // 1. 排序
        sort(nums.begin(),nums.end());
        // 2. 进行 a,b,c三个元素的选取
        for(int a=0;a0 && nums[a]==nums[a-1]) continue; // 【保证不重复】选取相同效果的元素
            // 在a确定的情况下，选取b后，c也就确定了。所有可以使用双指针b,c两个相向行走
            int c=n-1;
            for(int b=a+1;ba+1 && nums[b]==nums[b-1]) continue;// 【保证不重复】选取相同效果的元素
                while(b0){// 【3】选择第三个元素c
                    c--;
                }
                if(b==c) break; // 此情况就是nums[a]+nums[b]+nums[c]>0，
                //由于nums递增，后面元素只会越来越大，将不会存在b,c使得三者相加为0，都是>0的了
                if( c>b && nums[a]+nums[b]+nums[c]==0){
                    ans.push_back({nums[a], nums[b], nums[c]});
                }
            }
        }
        return ans;
    }
};
 
 
4. 寻找两个正序数组的中位数 
前往题源
 2022-01-12
 
 
class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        // 使用两个指针同时遍历两个数组，使用count记录当前的位置
        int count = 0;
        int a = 0,b = 0,la = nums1.size(),lb = nums2.size();
        int len = la+lb;
        double p=0,pre=0; // p记录当前工作元素值，pre为p的前一个元素值
        // 1.在循环里面就找到了中位数
        while(alen/2){
                if(len%2 ==1) return p;
                else return (p+pre)/2;
            }
        }
        // 2. 在循环外面找到了中位数
        while(a