Array-Easy

2020-02-26
Abstract： 更新部分Easy难度 Array相关题解

1. Two Sum

image-20200226115823526

解法一：暴力法

冒泡排序，送死写法，就不多说了

解法二：哈希表

为了最快得到target的index，HashMap是个好方法，$Time:O(n^2) Space:O(n^2)$

//原始版本为两遍Hash表，但是发现可以合写在一起
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for (int i=0;i<nums.length;i++){
            if (map.containsKey(nums[i])&&map.get(nums[i])!=i)
                return new int[] {i,map.get(nums[i])//此值的index及其对应满足条件的index
                };
            map.put(target-nums[i],i);//不满足的话存入Map准备下一次搜索
        }
        throw new IllegalArgumentException("no such answer!");
    }
}

83. Remove Duplicates from Sorted List

image-20200226144922682

解法一：双指针

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length<=1)return 1;//1的情况
        int len=1;//因为第一个必定是nums[0],所以从1开始
        for(int i=0;i<nums.length-1;i++){
            if (nums[i]!=nums[i+1]){
                nums[len]=nums[i+1];//每找到一个新的值，放到前面对应的位置
                len++;//更新最新前面的指针
            }
        }
        return len;
    }
}

27. Remove Element

image-20200226145029241

解法一：我的双指针

第一想到的虽然是覆盖，但还是鬼使神差得选择了交换

  1. 从后往前找一个非val的值
  2. 从前往后找一个等于val的值
  3. 二者交换（交换的方法很蠢，浪费时间和空间，不如直接覆盖）

缺点：需要考虑很多边界情况，而且还麻烦

class Solution {
    public int removeElement(int[] nums, int val) {
        //考虑特殊情况，0，1,2,空
        if(nums.length==1){
            if(nums[0]==val)return 0;
            else return 1;
        }
        int lo=0,hi=nums.length-1,count=0;
        while(lo<hi){
            //从后往前找
            while(nums[hi] == val){
                hi--;
                count++;  //目标值++
                if(hi<0){return nums.length-count;} 
                //注意如果已经找到最前面了就不要再找了，直接返回目前的结果
            }
            //从后往前找
            while(lo<hi && nums[lo]!=val){ //注意必须满足lo<hi
                lo++;
            }
            //交换
            int temp=nums[lo];
            nums[lo]=nums[hi];
            nums[hi]=temp;
        }
        return nums.length-count;
    }
}

解法二：官方双指针[改]

直接覆盖的方法，简单优雅

  1. 从前往后找一个等于val的值
  2. 用后排的一个值直接覆盖
class Solution {
    public int removeElement(int[] nums, int val) {
        int lo=0,hi=nums.length;
        while(lo<hi){
            if(nums[lo]==val){nums[lo]=nums[--hi];}//如果是val就用后面的值覆盖
            //就算后面的值也是val也没关系，因为下一轮覆盖还是会把它覆盖掉
            else lo++;
        }
        return hi;//最后返回最后一次覆盖的位置，即为删除后的长度
    }
}

35. Search Insert Position

image-20200226145151262

解法一：二分查找（虽然思想简单，但是边界问题搞人）

class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo=0,hi=nums.length-1,mi=0;
        if(target<=nums[lo]){return 0;}  //小于最小值按0处理
        if(target>nums[hi]){return hi+1;} //大于最大值按length处理
        while(lo<=hi){ //注意必须是 <= 否则会错过一次循环判定
            mi=(lo+hi)/2;
            if(target==nums[mi]){return mi;} //如果刚好相等，那返回该处索引
            else if(target<nums[mi]){hi=mi-1;} //二分查找模板
            else if(target>nums[mi]){lo=mi+1;}
        }
        //如果没有刚好相等的，要进行最后一轮判定
        if(nums[mi]<target)return mi+1; //小于target，要+1
        else return mi;
    }
}

53. Maximum Subarray

image-20200226145315266

解法一：分治

  1. 最大和序列可能的情况：左边界序列，右边界序列，中间序列
  2. 因此先计算左右边界序列的最大值，再递归地比较中间序列，就能找到最大的子序列和
class Solution {
    public int maxSubArray(int[] nums) {
        return maxSub(nums,0,nums.length-1);
    }

    public int maxSub(int[] nums,int lo,int hi){
        if(hi<lo){return Integer.MIN_VALUE;//注意越界后要返回一个最小的值，否则无法通过负数的情况
                 }// lo必须小于等于hi
        
        int maxLeft=nums[lo],maxRight=nums[hi],sumLeft=0,sumRight=0;//一些待用变量
        
        for(int i=lo;i<=hi;i++){//找到左边界的最大和序列
            sumLeft+=nums[i];
            maxLeft=Math.max(sumLeft,maxLeft);
            //if(sumLeft>maxLeft){
            //    maxLeft=sumLeft;
            //    indexLeft=i;
            //}
        }
        for(int i=hi;i>=lo;i--){//找到右边界的最大和序列
            sumRight+=nums[i];
            maxRight=Math.max(sumRight,maxRight);
            //if(sumRight>maxRight){
            //    maxRight=sumRight;
            //    indexRight=i;
            //}
        }
        int maxSide=Math.max(maxLeft,maxRight);
        return Math.max(maxSide,maxSub(nums,lo+1,hi-1)); //左右边界最大和序列 与 中间和序列 比较
    }
}

解法二：线性扫描

  1. 计算当前的和

  2. 比较最大值

  3. 如果当前和 小于等于0，那么和直接归零，因为前面的结果不能让后面更大了，因此也没有继续加和的必要了

  4. 时间复杂度：$O(N)$

class Solution {
    public int maxSubArray(int[] nums) {
        int sum=0,max=nums[0];
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];          //计算当前和
            max=Math.max(sum,max); //注意要先比较max，不然会导致sum=0和全负数的情况比较，结果错误
            if(sum<=0){sum=0;}     //小于0就可以滚蛋了，因为肯定没有后面的和大
        }
        return max;
    }
}

88. Merge Sorted Array

image-20200302231613636

解法一：排序

复制数组，然后排序就行了，简单粗暴

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
    }
}

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int len = m + n;
        for(int i = m; i < len; i++) 
            nums1[i] = nums2[i - m];
        std::sort(nums1.begin(), nums1.end());
    }
};

解法二：双指针

要点是从后往前填

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int len = m + n, p1 = m - 1, p2 = n - 1;
        for(int i = len - 1; i > -1; i--) {
            if(p1 < 0) nums1[i] = nums2[p2--];
            else if(p2 < 0) nums1[i] = nums1[p1--];
            else if(nums1[p1] < nums2[p2])
                nums1[i] = nums2[p2--];
            else
                nums1[i] = nums1[p1--];
        }
        
    }
};

169. Majority Element

image-20200303001955825

解法一：排序

排序之后，相同的数将会连续排列，就能方便地进行统计了

class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length==1)return nums[0];
        Arrays.sort(nums);
        int num=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]==nums[i-1]){
                if(++num>nums.length/2)return nums[i];
            }
            else num=1;
        }
        return -1;
    }
}

解法二：投票法

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int curr = -1, curr_val = 0;
        for(int i : nums){
            if(curr_val <= 0) curr = i;
            if(i == curr) 
                curr_val++;
            else 
                curr_val--;
        }
        return curr;
    }
};

189. Rotate Array

image-20200505193321501

解法一：暴力模拟

用类似冒泡法的方法每轮从末尾移动到第一个，一共n轮，由于数据规模达到20000，超时

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        for(int i = 0; i < k; i++){
            for(int j = nums.size() - 1; j > 0; j--){
                int tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp; 
            }
        }
    }
};

解法二：辅助空间

后k个移到辅助数组的前k个，剩余移到后面，再把辅助数组移回原数组

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        vector<int> helper = vector<int>(nums.size());
        for(int i = 0; i < k; i++)
            helper[i] = nums[nums.size() - k + i];
        for(int i = k; i < nums.size(); i++)
            helper[i] = nums[i - k];
        for(int i = 0; i < nums.size(); i++)
            nums[i] = helper[i];
    }
};

283. Move Zeroes

image-20200517204110963

解法一：冒泡

两两交换，一直换到末尾

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int start = 0, end = nums.size() - 1;
        while(start < end) {
            if(nums[start] == 0) {
                for(int i = start; i < nums.size() - 1; i++)
                    ::swap(nums[i], nums[i + 1]);
                end--;
            }
            else start++;
        }
    }
};

解法二：双指针

按顺序先把k个非零元素放在前k位，再把后k位置零，但还是多遍历了 len - k - 1次

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int idx = -1;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != 0) nums[++idx] = nums[i];
        }
        for(int i = idx + 1; i < nums.size(); i++)
            nums[i] = 0;
    }
};

再优化

只需要一次遍历

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int idx = -1;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != 0) ::swap(nums[++idx], nums[i]);
        }
    }
};

448. Find All Numbers Disappeared in an Array

image-20200926221245248

Solution-1

Because of the val range’s specialty (1 <= a[i] <= n), the trick of it is convert positive val’s corresponding postion to negative one, marking the val which you have check

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        // convert cooresponding pos to negative form
        for(int i = 0; i < nums.size(); ++i) 
            nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
        // remaining postive pos show the 
        for(int i = 0; i < nums.size(); ++i) 
            if(nums[i] > 0) res.push_back(i + 1);
        return res;
    }
};

581. Shortest Unsorted Continuous Subarray

image-20200926222308447

Solution-1

Sort the array and check same postion of left side and rigth side, r - l + 1 show the answer

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> t = nums;
        std::sort(nums.begin(), nums.end());
        int l = 0, r = nums.size() - 1;
        while(l <= r && nums[l] == t[l]) ++l;
        while(l <= r && nums[r] == t[r]) --r;
        return r - l + 1;
    }
};

Solution-2

  • find the last position which didn’t incresing
  • find the firts position which didn’t declinling
  • r - l + 1 show the ans of the problem, expect for case of l == r which show origin array is ascending array
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int len = nums.size(), l = 0, r = 0;
        for(int i = 1, max = nums[0]; i < len; ++i) {
            if(nums[i] < max) r = i;
            max = std::max(max, nums[i]);
        }
        for(int i = len - 2, min = nums[len - 1]; i > -1; --i) {
            if(nums[i] > min) l = i;
            min = std::min(min, nums[i]);
        }
        return r == l ? 0 : r - l + 1;
    }
};
© 2020 Overyam - Powered by Hexo - Theme Chan