[Leetcode][Array--1]数组相关题目汇总/分析/

作者: 奔跑的程序媛A | 来源:发表于2019-06-09 06:53 被阅读0次

[Leetcode][Array--1]数组相关题目汇总/分析/
[Leetcode][Array--2]数组相关题目汇总/分析/
LeetCode 477 Total Hamming Dista
LeetCode 473 Matchsticks to Squa
LeetCode 401 Binary Watch
LeetCode 461 Hamming Distance
[Leetcode][栈]相关题目汇总/分析/总结
[Leetcode][链表]相关题目汇总，分析，总结
4.双指针（四）
7.数学（七）

Find
- 287 Find the Duplicate Number
- 4 Median of Two Sorted Arrays
- 274 H-Index
- 275 H-Index II
- 41 First Missing Positive
- 295 Find Median from Data Stream
Remove/Rotate
- 27 Remove Element
- 26 Remove Duplicates from Sorted Array
- 80 Remove Duplicates from Sorted Array II
- 189 Rotate Array
Sort
- 88 Merge Sorted Array
- 75 Sort Colors
- 283 Move Zeroes
- 376 Wiggle Subsequence
- 324 Wiggle Sort II
Count / Subarray / Product
- 53 Maximum Subarray
- 643 Maximum Average Subarray I
- 209 Minimum Size Subarray Sum
- 238 Product of Array Except Self
- 152 Maximum Product Subarray
- 628 Maximum Product of Three Numbers
- 713 Subarray Product Less Than K
- 560 Subarray Sum Equals K
- 228 Summary Ranges

[Find]

#287 Find the Duplicate Number

Sol Cycle Detection
LinkedList Cycle II
时间复杂度O(n) 空间复杂度O(1)

class Solution {
    public int findDuplicate(int[] nums) {
        int fast = nums[0];
        int slow = nums[0];
        do{
            fast = nums[nums[fast]];
            slow = nums[slow];
        }while(fast!=slow);
        
        fast = nums[0];
        while(fast!=slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return fast;
    }
}

#4 Median of Two Sorted Arrays

两个有序数组，数组大小分别为m和n，找到两个数组的中位数，要求时间复杂度为O(log (m+n))

Sol Binary Search
A, B数组以点i，j拆分。A，B左半部分组成leftpart，右半部分组成right part

leftpart与leftpart长度相等
max(leftpart) < min(rightpart)
满足两点，则median为max(leftpart) 或者 min(rightpart) /2+ max(leftpart) /2

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if(n < m){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
            int tmp_len = m;
            m = n;
            n = tmp_len;
        }
        int iMin = 0, iMax = m, half = (m+n+1)/2;
        while(iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = half - i;
            if(i < iMax && nums2[j-1] > nums1[i]) {
                iMin = i+1; // i is too small
            }else if(i > iMin && nums1[i-1] > nums2[j]) {
                iMax = i-1;
            }else {
                int maxLeft = 0;
                if(i == 0) maxLeft = nums2[j-1];
                else if(j == 0) maxLeft = nums1[i-1];
                else maxLeft = Math.max(nums1[i-1], nums2[j-1]);
                if((m+n) % 2 == 1) return maxLeft;
                int minRight = 0;
                if(i == m) minRight = nums2[j];
                else if(j == n) minRight = nums1[i];
                else minRight = Math.min(nums1[i], nums2[j]);
                return (minRight + maxLeft) / 2.0;
            }
        }
        return 0.0;
        
    }
}

#274 H-Index

Sol Array.sort
时间复杂度O(nlogn)空间复杂度O(1)

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int N = citations.length;
        for(int i = 0; i < N; i++){
            if(citations[i] >= N-i) return N-i;
        }
        return 0;
    }
}

Sol Bucket sort桶排序
桶数组位置i里面存放原数组i的个数，即bucket[i] = count(citations[j]) which citations[j] = i; 注意大于等于len(array)的计数

class Solution {
    public int hIndex(int[] citations) {
        int N = citations.length;
        int[] bucket = new int[N+1];
        for(int i = 0; i < N; i++){
            bucket[Math.min(citations[i], N)]++;
        }
        int count = 0;
        for(int i = N; i >= 0; i--){
            count += bucket[i];
            if(count >= i) return i;
        }
        return 0;
    }
}

#275 H-Index II

Sol 遍历
O(n)
(citations.length -i) is the number of papers that has been citated more than citations[i] times.

class Solution {
    public int hIndex(int[] citations) {
        int N = citations.length;
        for(int i = 0; i < N; i++){
            if(citations[i] >= N-i)
                return N-i;
        }
        return 0;
    }
}

Sol 二分查找法
O(logn)

class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) return 0;
        int start = 0;
        int end   = citations.length-1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(citations[mid] >= citations.length - mid) end = mid - 1;
            else start = mid + 1;
        }
        return citations.length - start;
    }
}

#41 First Missing Positive

未排序数组，找出不存在的最小的数。

Sol 遍历
消失的数一定<=n+1 空间复杂度O(1)

<=0得数改为len+1
nums[nums[i]]如果<len，则“归位”==> nums[nums[i]] * -1
num[i] > 0 则i+1为结果
否则为len+1

    public int firstMissingPositive(int[] nums) {
        int N = nums.length;
        for(int i = 0; i < N; i++){
            if(nums[i] <= 0) nums[i] = N+1;
        }
        for(int i = 0; i < N; i++){
            if(Math.abs(nums[i]) <= N && nums[Math.abs(nums[i])-1] > 0) 
                nums[Math.abs(nums[i])-1] *= -1;
        }
        for(int i = 0; i < N; i++){
            if(nums[i] > 0) return i+1;
        }
        return N+1;
    }

#295 Find Median from Data Stream

Two Heaps
A max-heap to store the smaller half of the input numbers
A min-heap to store the larger half of the input numbers
PriorityQueue
new PriorityQueue<>((n1, n2) -> n1 - n2);

class MedianFinder {
    PriorityQueue<Integer> asce;
    PriorityQueue<Integer> desc;
    /** initialize your data structure here. */
    public MedianFinder() {
        asce = new PriorityQueue<>((n1, n2) -> n1 - n2);//larger part, minimum peek
        desc = new PriorityQueue<>((n1, n2) -> n2 - n1);
    }
    
    public void addNum(int num) {
        asce.offer(num);
        desc.offer(asce.poll());
        if(desc.size() > asce.size()) {
            asce.offer(desc.poll());
        }
        
    }
    
    public double findMedian() {
        if(desc.size() == asce.size()) return (asce.peek() + desc.peek()) / 2.0;
        else return asce.peek();
    }
}

[Remove/Rotate]

#27 Remove Element

Sol 双指针

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        for(int j = 0; j < nums.length; j++){
            if(nums[j] != val){
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}

#26 Remove Duplicates from Sorted Array

Sol 双指针

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for(int j = 1; j < nums.length; j++){
            if(nums[i] != nums[j]){
                nums[++i] = nums[j];
            }
        }
        return i+1;
    }
}

#80 Remove Duplicates from Sorted Array II

Sol 双指针

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        int limit = 0;
        for(int j = 1; j < nums.length; j++){
            if(nums[i] != nums[j]){
                nums[++i] = nums[j];
                limit = 0;
            }else if(nums[i] == nums[j] && limit < 1){
                limit++;
                nums[++i] = nums[j];
            }
        }
        return i+1;
    }
}

#189 Rotate Array

Sol. Reverse
空间复杂度O(1)时间复杂度O(n)

class Solution {
    public void rotate(int[] nums, int k) {
        k = k %nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.length -1);
    }
    public void reverse(int[] nums, int start, int end){
        while(start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}

[Sort]

#88 Merge Sorted Array

Sol1 Insertion Sort
Time O(n * m)
Space O(1)

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i = 0; i < n; i++){
            int cur = nums2[i];
            int j = m-1;
            while(j >= 0 && cur < nums1[j]){
                nums1[j+1] = nums1[j];
                j--;
            }
            nums1[j+1] = cur;
            m++;
        }
    }
}

Sol new Array
Time O(m+n)
Space O(m+n)

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] res = new int[m+n];
        int p1 = 0, p2= 0;
        for(int i = 0; i < m+n; i++){
            if(p1 < m || p2 < n){
                if(p1 >= m) res[i] = nums2[p2++];
                else if(p2 >= n) res[i] = nums1[p1++];
                else if(nums1[p1] < nums2[p2]){
                    res[i] = nums1[p1++];
                }else{
                    res[i] = nums2[p2++];
                }
            }
        }
        System.arraycopy(res, 0, nums1, 0, m+n);
    }
}

#75 Sort Colors

Sol Dijkstra
move all red color to front and blue color to last, so white color will be in middle

    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        int cur = 0;
        while(cur <= right) {
            if(nums[cur] == 0){
                int tmp = nums[left];
                nums[left] = nums[cur];
                nums[cur] = tmp;
                cur++;
                left++;
            }else if(nums[cur] == 2){
                int tmp = nums[right];
                nums[right] = nums[cur];
                nums[cur] = tmp;
                right--;
            }else cur++;
        }
    }

#283 Move Zeroes

Sol spaceO(1)

        int n = nums.length;
        int i = 0;
        for(int j = 0; j < n; j++){
            if(nums[j] != 0){
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i++] = tmp;
            }
        }

#376 Wiggle Subsequence

Sol DP

i点为up or down
up position： nums[i] > nums[i-1]
down position： it means nums[i] < nums[i-1]
更新长度
因为仅与前一个down/up有关
所以无需数组
up = down + 1
down = up + 1
3.O(n)时间复杂度，O(1)空间复杂度

    public int wiggleMaxLength(int[] nums) {
        if(nums.length < 2) return nums.length;
        int down = 1, up = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[i-1]) up = down + 1;
            if(nums[i] < nums[i-1]) down = up + 1;
        }
        return Math.max(up, down);
    }

Sol2 Greedy
subsequence里选最高/低峰

public int wiggleMaxLength(int[] nums) {
        if(nums.length < 2) return nums.length;
        int prediff = nums[1] - nums[0];
        int res = 2;
        if(prediff == 0) res = 1;
        for(int i = 2; i < nums.length; i++){
            int diff = nums[i] - nums[i-1];
            if((prediff <= 0 && diff > 0) || (prediff >= 0 && diff < 0)){
                res++;
                prediff = diff;
            }
        }
        return res;
    }

#324 Wiggle Sort II

Sol Quick Select + two pointer
Quick Select找中位数，两指针分别记录最后的odd与even点，遍历数组，更新
odd = nums.length % 2 == 0 ? nums.length - 2: nums.length - 1
even = 1
(开始用odd=0，even=1，出现了131322的排序结果，出现错误)

public void wiggleSort(int[] nums) {
        if(nums.length < 2) return;
        int k = nums.length % 2 == 0 ? nums.length / 2 - 1 : nums.length / 2;
        median(nums, 0, nums.length-1, k);
        int mid = nums[k]; //median
        int cur = 0, odd = nums.length % 2 == 0 ? nums.length - 2: nums.length - 1, even = 1;
        while(cur < nums.length){
            if(nums[cur] < mid && !(cur >= odd && cur % 2 == 0)){
                int tmp = nums[cur];
                nums[cur] = nums[odd];
                nums[odd] = tmp;
                odd -= 2;
            }else if(nums[cur] > mid && !(cur <= even && cur % 2 == 1)){
                int tmp = nums[cur];
                nums[cur] = nums[even];
                nums[even] = tmp;
                even += 2;
            }else cur++;
        }
        
        System.out.print(mid);
    }
    public void median(int[] nums, int start, int end, int k) {
        int left = start, right = end;
        if(left == right) return;
        int cur = left;
        int pivot = nums[(left + right) / 2];
        while(cur < right){
            if(nums[cur] < pivot) {
                int tmp = nums[cur];
                nums[cur] = nums[left];
                nums[left] = tmp;
                cur++;
                left++;
            }else if(nums[cur] > pivot) {
                int tmp = nums[cur];
                nums[cur] = nums[right];
                nums[right] = tmp;
                right--;
            }else{
                cur++;
            }
        }
        if(left >= k) median(nums, start, left, k);
        if(cur <= k) median(nums, cur, end, k);
        return;
    }

[Count / Subarray / Product]

#53 Maximum Subarray

Sol 遍历
nums[i] > tmp_res, tmp_res = nums[i]

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0) return 0;
        int res = nums[0];
        int max_res = res;
        for(int i = 1; i < nums.length; i++){
            res += nums[i];
            if(nums[i] > res) {
                res = nums[i];
            }
            if(res > max_res){
                max_res = res;
            }
        }
        return max_res;
    }
}

#643 Maximum Average Subarray I

Sol Sliding Window
sum(nums[i...i+k]) = x;
sum(nums[i+1...i+k+1]) = x-nums[i]+num[i+k+1];

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double tmp = 0;
        for(int i = 0; i < k; i++){
            tmp += nums[i];
        }
        double res = tmp;
        for(int i = k; i < nums.length; i++){
            tmp = tmp - nums[i-k] + nums[i];
            res = Math.max(tmp, res);
        }
        return res/k;
    }
}

#209 Minimum Size Subarray Sum

Sol 遍历
==》 two pointer
start记录subarray起始点
i记录遍历的位置
sum存放和

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int res = Integer.MAX_VALUE;
        int start = 0;
        int sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= s) {
                res = Math.min(res, i - start + 1);
                sum -= nums[start++];
            }
        }
        
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

#238 Product of Array Except Self

要求without division and in O(n)

Sol O(1) space approach
L与R分别记录i点左边右边的乘积
第一次遍历，res[i]存放i点左边的乘积，第二次，R记录右边的乘积同时更新res

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] res = new int[size];
        res[0] = 1;
        // int L = 1;
        for(int i = 1; i < size; i++){
            res[i] = res[i-1] * nums[i-1];
        }
        int R = 1;
        for(int i = size - 1; i >= 0; i--){
            res[i] = res[i] * R;
            R = R * nums[i];
        }
        return res;
    }
}

#152 Maximum Product Subarray

注意负数相乘为正数，可能乘积变最大

So DP
max记录最大乘积，min记录最小乘积
max = Math.max(nums[i], max * nums[i], min * nums[i])
min = Math.min(nums[i], min * nums[i], max * nums[i]);

class Solution {
    public int maxProduct(int[] nums) {
        int res = nums[0];
        int min = nums[0], max= nums[0];
        for(int i = 1; i < nums.length; i++){
            int tmp_max = max;
            max = Math.max(nums[i], Math.max(nums[i] * max, nums[i] * min));
            min = Math.min(nums[i], Math.min(nums[i] * tmp_max, nums[i] * min));
            res = Math.max(max, res);
        }
        return res;
    }
}

#628 Maximum Product of Three Numbers

Sol 遍历数组
O(n)记录最小的两个点，最大的三个点

class Solution {
    public int maximumProduct(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for(int n:nums){
            if(n<=min1){
                min2 = min1;
                min1 = n;
            }else if(n <= min2) min2 = n;
            
            if(n >= max1){
                max3 = max2;
                max2 = max1;
                max1 = n;
            }else if(n >= max2){
                max3 = max2;
                max2 = n;
            }else if(n >= max3){
                max3 = n;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}

#713 Subarray Product Less Than K

Sol Sliding Window
找到每个点right对应的left，是的left为最小的index满足nums[left] * nums[left + 1] * ... * nums[right] 小于 k，更新count += right-left+1

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k<=1) return 0;
        int res = 0, pro  = 1, left = 0;
        for(int right = 0; right < nums.length; right++){
            pro *= nums[right];
            while(pro >= k){
                pro /= nums[left++];
            }
            res += right-left+1;
        }
        return res;
    }

#560 Subarray Sum Equals K

Sol Cummulative sum
Time O(n^2)
Space O(1)

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            for(int j = i; j < nums.length; j++){
                sum += nums[j];
                if(sum == k) count++;
            }
        }
        return count;
    }
}

Sol HashMap
TimeO(n) SpaceO(n)

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1);
        int sum = 0, count = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(hash.containsKey(sum-k)) count+=hash.get(sum-k);
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

#228 Summary Ranges

Sol 遍历
Time O(n)
Space O(1)

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        if(nums.length == 0) return res;
        int start = nums[0], end = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(nums[i] - 1 == nums[i-1]){
                end=nums[i];
            }else{
                if(start == end) res.add(start+"");
                else res.add(start + "->" + end);
                start = nums[i];
                end = nums[i];
            }
        }
        if(start == end) res.add(start+"");
        else res.add(start + "->" + end);
        return res;
    }
}

[Leetcode][Array--1]数组相关题目汇总/分析/
目录 Find287 Find the Duplicate Number4 Median of Two Sort...
[Leetcode][Array--2]数组相关题目汇总/分析/
目录 Interval56 Merge Intervals57 Insert Interval915 Partit...
LeetCode 477 Total Hamming Dista
LeetCode 排列组合题目汇总LeetCode 数字题目汇总LeetCode 动态规划题目分类汇总干货！...
LeetCode 473 Matchsticks to Squa
LeetCode 排列组合题目汇总LeetCode 数字题目汇总LeetCode 动态规划题目分类汇总干货！...
LeetCode 401 Binary Watch
LeetCode 排列组合题目汇总LeetCode 数字题目汇总LeetCode 动态规划题目分类汇总干货！...
LeetCode 461 Hamming Distance
LeetCode 排列组合题目汇总LeetCode 数字题目汇总LeetCode 动态规划题目分类汇总干货！...
[Leetcode][栈]相关题目汇总/分析/总结
题目汇总以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。目前范围：Leetcode前150题 ...
[Leetcode][链表]相关题目汇总，分析，总结
题目汇总以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。目前范围：Leetcode前150题 ...
4.双指针（四）
https://leetcode-cn.com/tag/two-pointers/题目汇总350. 两个数组的交集...
7.数学（七）
题目汇总https://leetcode-cn.com/tag/math/523. 连续的子数组和中等[✔]535...

[Leetcode][Array--1]数组相关题目汇总/分析/

目录

[Find]

#287 Find the Duplicate Number

#4 Median of Two Sorted Arrays

#274 H-Index

#275 H-Index II

#41 First Missing Positive

#295 Find Median from Data Stream

[Remove/Rotate]

#27 Remove Element

#26 Remove Duplicates from Sorted Array

#80 Remove Duplicates from Sorted Array II

#189 Rotate Array

[Sort]

#88 Merge Sorted Array

#75 Sort Colors

#283 Move Zeroes

#376 Wiggle Subsequence

#324 Wiggle Sort II

[Count / Subarray / Product]

#53 Maximum Subarray

#643 Maximum Average Subarray I

#209 Minimum Size Subarray Sum

#238 Product of Array Except Self

#152 Maximum Product Subarray

#628 Maximum Product of Three Numbers

#713 Subarray Product Less Than K

#560 Subarray Sum Equals K

#228 Summary Ranges

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读