leetcode——数据结构——数组

寻找两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))——看到时间复杂度包含log 要用分治算法，findKth
示例 1:
nums1 = [1, 3]
nums2 = [2]
关键：学会写在两个数组中，寻找Kth数字。

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length, left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) return nums2[j + k - 1];
        if (j >= nums2.length) return nums1[i + k - 1];
        if (k == 1) return Math.min(nums1[i], nums2[j]);
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }
}

【3. 无重复字符串的最大长度】滑动窗口
问题：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
思路：
所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！

 public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
        
    }

2sum 3sum 4sum
盛最多水的容器 —— 对撞指针
题目：给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
解题：头尾各一个指针：首指针i指向数组中的第一个元素，尾指针j指向数组中的最后一个元素。每一次循环都舍弃索引i和索引j中较短的那一条边。
代码：

public int maxArea(int[] height) {
        int n = height.length;
        int i = 0;
        int j = n - 1;
        int area = (n - 1) * Math.min(height[i], height[j]);
        while(i < j) {
            area = Math.max(area, (j - i) * Math.min(height[i], height[j]));
            if(height[i] < height[j]) {
                i++;
            }else {
                j--;
            }
        }
        return area;
    }

从排序数组中删除重复元素
题目：给定一个有序数组，删除重复内容，使每个元素只出现一次，并返回新的长度。
不要为其他数组分配额外的空间，您必须通过在 O（1）额外的内存中就地修改输入数组来实现这一点。
解题：采用两个标记点 number 和 i ，number记录不重复元素的位置，i从number的下一个开始遍历数组，如果i位置的数字等于number位置的数字，说明该数字重复出现，不予处理；如果i位置的数字不等于number位置的数字，说明该数字没有重复，需要放到l的下一位置，并使number加1。
代码：

int number = 0;
for(int i =0; i<nums.length;i++){
    // 相邻两个值比较，不同才做统计操作
    if(nums[i]!=nums[number]){
       number++;
       nums[number] = nums[i];
    }
}
// 不同数字为总量= number+1
return ++number;

题目变形：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

int removeDuplicates(vector<int>& nums) {
        if (nums.empty())
            return 0;
        // 一次遍历，[0,number)为最终的每个元素最多出现两次的数组
        int n = nums.size();
        int number = 1; 
        int count = 1; // 计数器
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[number  - 1] && count == 1) {
                nums[number ++] = nums[i];
                count++;
            }
            else if (nums[i] != nums[number  - 1]) {
                nums[number ++] = nums[i];
                count = 1;
            }   
        }
        return number ;

分类颜色
题目：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

思路：维护三个指针

void sortColors2(vector<int>& nums) {
        int zero_index = -1;
        int n = nums.size();
        int two_index = n;
        for (int i = 0; i < n;) {
            if (i >= two_index)
                return;
 
            if (nums[i] == 1)
                i++;
            else if (nums[i] == 0) {
                swap(nums[++zero_index], nums[i]);
                i++;
            }
            else if (nums[i] == 2) {
                swap(nums[i], nums[--two_index]);
            }
        }
    }

长度最小的子数组——双指针、滑动指针
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:
输入:
s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组
[4,3]
代码：

int minSubArrayLen(int s, vector<int>& nums) {
        // 根据当前nums[i,j]的值与s的大小关系决定i,j索引的更新
        int i = 0;
        int j = -1;
        int minLen = nums.size() + 1;
        int sum = 0;
        int n = nums.size();
        while (i < n) {
            // 当前的滑动窗口sum小于s，那么就要滑动j，使得sun增加
            if (sum < s) {  // 如果sum不够，则增加j
                sum += nums[++j];
                if (j >= n) // 退出条件
                    break;
            }
            else { // 如果sum够大，则增加i
                minLen = std::min(minLen, j - i + 1);
                sum -= nums[i++];
            }
        }
 
        return minLen == n + 1 ? 0 : minLen;
    }

数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入:
[3,2,1,5,6,4] 和
k = 2
输出: 5

示例 2:
输入:
[3,2,3,1,2,4,5,5,6] 和
k = 4
输出: 4

思路：
针对这个题目，我们首先想到的就是先用排序算法对数据从大到小进行排序，然后直接返回降序后的第 K 个元素即可。
另外，我们也可以借鉴快速排序的思想。每次选取一个 pivot，将大于 pivot 的数放在 pivot 左边，将小于 pivot 的数放在 pivot 右边。这时：
(1)如果 pivot 正好是第 K 个数据，则 pivot 就是数组中的第 K 个最大元素；
(2)如果 pivot 所在的位置小于 K ，则说明数组中的第 K 个最大元素位于 pivot 的右边。此时，假设 pivot 的位置为 which_max，which_max 是几就代表 pivot 是数组中的第几个最大元素。这时候，我们再从 pivot 右边的数据中找到第 (K-which_max) 个最大元素即可；
(3)如果 pivot 所在的位置大于 K ，则说明数组中的第 K 个最大元素位于 pivot 的左边。这时候，pivot 左边的数据全部大于 pivot，我们继续从 pivot 左边的数据中找第 K 个最大元素即可

 int findKthLargest(vector<int>& nums, int k) {
    
        return quick_sort(nums, 0, nums.size()-1, k);
    }
    
    // 第一种快排思想
    int quick_sort(vector<int>& data, int left, int right, int k)
    {
        int i = left;
        int j = right;
        int pivot = data[right];
        int len = right - left + 1;

        if (left < right)
        {  
            // 从大到小对数组进行快排
            while(i < j)
            {
                while(i < j && data[i] >= pivot) // 从左往右找第一个比 pivot 小的数
                {
                    i++;
                }
                if (i < j)
                {
                    data[j--] = data[i];
                }

                while(i < j && data[j] <= pivot) // 从右往左找第一个比 pivot 大的数
                {
                    j--;
                }
                if (i < j)
                {
                    data[i++] = data[j];
                }
            }
            
            data[i] = pivot; // 此时 i == j

            // pivot 此时位于索引 i 处，i - left + 1 表示 pivot 是第几大的数
            int which_max = i - left + 1;
            if (which_max == k) // pivot 正好是第 k 大的数
            {
                return pivot;
            }
  
            // 第 k 大的数在 pivot 右边，问题转化为找右边数组第 (k - which_max) 大的元素
            // 比如 pivot 是第四大的数，要找第五大的数，则继续找右边数组第一大的数即可
            else if(which_max < k)
            {
                return quick_sort(data, i + 1, right, k - which_max);
            }
            
            // 第 k 大的数在 pivot 左边，问题转化为找左边数组第 k 大的元素
            // 比如 pivot 是第三大的数，要找第二大的数，则继续找左边数组第二大的数即可
            else
            {
                return quick_sort(data, left, i - 1, k);
            }
        }
        else
        {
            return pivot;
        }
    }

(215). 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
(1) 快排思路
复杂度分析
时间复杂度:O(n); 空间复杂度:O(logn)，递归使用栈空间的空间代价的期望为 O(logn)。

class Solution {
    Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    public int quickSelect(int[] a, int l, int r, int index) {
        int q = randomPartition(a, l, r);
        if (q == index) {
            return a[q];
        } else {
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }

    public int randomPartition(int[] a, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;
        swap(a, i, r);
        return partition(a, l, r);
    }

    public int partition(int[] a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a, ++i, j);
            }
        }
        swap(a, i + 1, r);
        return i + 1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

(414) 第三大的数
给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。
示例 1：
输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1
(1)思路一：借用TreeSet（红黑树） O(n)
比较好想的思路
**维护一个只有3个元素的TreeSet，如果大于三个元素就就把Set中的最小最小值remove掉。
**最后如果Set中元素小于3就返回Set最大值，否则返回最小值。
时间复杂度： O(n * log3) == O(n)

class Solution {
    public int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0) throw new RuntimeException("error");

        TreeSet<Integer> set = new TreeSet<>();
        for (Integer elem : nums) {
            set.add(elem);
            if (set.size() > 3) set.remove(set.first());
        }
        
        return set.size() < 3 ? set.last() : set.first();   // set.last() 里面最大的元素
    }
}

(2)思路二：
用三个变量来存放第一大，第二大，第三大的元素的变量，分别为one, two, three；
遍历数组，若该元素比one大则往后顺移一个元素，比two大则往往后顺移一个元素，比three大则赋值个three；最后得到第三大的元素，若没有则返回第一大的元素。

class Solution {
    private long MIN = Long.MIN_VALUE;    // MIN代表没有在值
    
    public int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0) throw new RuntimeException("nums is null or length of 0");
        int n = nums.length;
        
        int one = nums[0];
        long two = MIN;
        long three = MIN;
        
        for (int i = 1; i <  n; i++) {
            int now = nums[i];
            if (now == one || now == two || now == three) continue;    // 如果存在过就跳过不看
            if (now > one) {
                three = two;
                two = one;
                one = now;
            } else if (now > two) {
                three = two;
                two = now;
            } else if (now > three) {
                three = now;
            }
        }

        if (three == MIN) return one;  // 没有第三大的元素，就返回最大值
        return (int)three;
    }
}