Men的博客

欢迎光临！

0%

数组

发表于

旋转数组

本题的难点在于如何处理数组，一个是开辟另一个数组进行处理，另一个是多次旋转数组实现
方法 1：暴力
最简单的方法是旋转 k 次，每次将数组旋转 1 个元素。
public class Solution {
    public void rotate(int[] nums, int k) {
        int temp, previous;
        for (int i = 0; i < k; i++) {
            previous = nums[nums.length - 1];
            for (int j = 0; j < nums.length; j++) {
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    }
}
方法 2：使用额外的数组
public class Solution {
    public void rotate(int[] nums, int k) {
        int[] a = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            a[(i + k) % nums.length] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = a[i];
        }
    }
}
方法 3：使用环状替换
public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int count = 0;
        for (int start = 0; count < nums.length; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.length;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }
}
方法 4：使用反转
原始数组                  : 1 2 3 4 5 6 7
反转所有数字后             : 7 6 5 4 3 2 1
反转前 k 个数字后          : 5 6 7 4 3 2 1
反转后 n-k 个数字后        : 5 6 7 1 2 3 4 --> 结果

public class Solution {
    public void rotate(int[] nums, int 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 temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

数组迭代

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

public class NestedIterator implements Iterator<Integer> {
Queue<Integer> res = new LinkedList<>();

public NestedIterator(List<NestedInteger> nestedList) {
    for(NestedInteger temp : nestedList)
        DFS(temp);
}

@Override
public Integer next() {
    return res.poll();
}

@Override
public boolean hasNext() {
    if(res.isEmpty())
        return false;
    return true;
    
}
public void DFS(NestedInteger Node){
    /* 深度遍历 */
    if(Node.isInteger())
        res.offer(Node.getInteger());
    for(NestedInteger temp :Node.getList())
        DFS(temp);
}
}

调整数组顺序使奇数位于偶数前面

本题的难点在入如何交换数据，采用i，j双指针，直到都不为奇偶才交换
public int[] exchange(int[] nums) {
       if(nums.length == 0) return nums;
       int i = 0,j = nums.length-1;
       while(i != j){
           while(nums[i] %2 != 0 && i<j ){
               i++;
           }
           while(nums[j] %2 == 0 && i<j ){
               j--;
           }
           if(i<j){
               int temp = nums[i];
               nums[i] = nums[j];
               nums[j] = temp;
           }
       }
       return nums;
   }

数组中出现次数超过一半的数字

   哈希表统计法，用 HashMap 统计各数字的数量
   数组排序法：由于众数的数量超过数组长度一半，
   因此 数组中点的元素 一定为众数
   摩尔投票法：核心理念为 “正负抵消” 
   当 n=x ： 抵消的所有数字中，有一半是众数    
   n不等x ： 抵消的所有数字中，少于或等于一半是众数 x
   利用此特性，每轮假设都可以 缩小剩余数组区间 。当遍历完成时，最后一轮假
   设的数字即为众数（由于众数超过一半，最后一轮的票数和必为正数）

   public int majorityElement(int[] nums) {
       int x = 0, votes = 0;
       for(int num : nums){
           if(votes == 0) x = num;
           votes += num == x ? 1 : -1;
       }
       return x;
   }

连续子数组的最大和

    这种最适合动态规划了，慢慢的变化，将前面的结构给到nums[i]
       输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
   class Solution {
       public int maxSubArray(int[] nums) {
           int res = nums[0];
           for(int i = 1; i < nums.length; i++) {
               nums[i] += Math.max(nums[i - 1], 0);
               res = Math.max(res, nums[i]);
           }
           return res;
       }
   }

1～n整数中1出现的次数

从个位到最高位的变量递推公式为
# 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
# 将 cur 加入 low ，组成下轮 low
# 下轮 cur 是本轮 high 的最低位
# 将本轮 high 最低位删除，得到下轮 high
# 位因子每轮 × 10
   class Solution {
       public int countDigitOne(int n) {
           int digit = 1, res = 0;
           int high = n / 10, cur = n % 10, low = 0;
           while(high != 0 || cur != 0) {
               if(cur == 0) res += high * digit;
               else if(cur == 1) res += high * digit + low + 1;
               else res += (high + 1) * digit;
               low += cur * digit;
               cur = high % 10;
               high /= 10;
               digit *= 10;
           }
           return res;
       }
   }

数字序列中某一位的数字

   数字以0123456789101112131415…的格式序列化到一个字符序列中
   迭代 + 求整 / 求余
       count=9×start×digit，num = start + (n - 1)

       class Solution {
       public int findNthDigit(int n) {
           int digit = 1;
           long start = 1;
           long count = 9;
           while (n > count) { // 1.
               n -= count;
               digit += 1;
               start *= 10;
               count = digit * start * 9;
           }
           long num = start + (n - 1) / digit; // 2.
           return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
       }
   }

和为s的两个数字

        双指针法，分别指向数组的两端，如果两个数的和大于target则j--如果小于target则i++，直至相等 
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while(i < j) {
            int s = nums[i] + nums[j];
            if(s < target) i++;
            else if(s > target) j--;
            else return new int[] { nums[i], nums[j] };
        }
        return new int[0];
    }
}

给定两个数组，编写一个函数来计算它们的交集。

方法一：哈希表
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
方法二：排序
如果两个数组是有序的，则可以便捷地计算两个数组的交集。
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX, sec = INT_MAX;     
        for(int n : nums)                       //
        {
            if(n <= first)  first = n;          
            else
            {
                if(n <= sec )   sec = n;        
                else   return true;
            }
        }
        return false;

    }
};

逆波兰表达式

是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
class Solution {
    //纯数组模拟栈实现(推荐)   3 ms    36 MB
    public static int evalRPN(String[] tokens) {
        int[] numStack = new int[tokens.length / 2 + 1];
        int index = 0;
        for (String s : tokens) {
            switch (s) {
            case "+":
                numStack[index - 2] += numStack[--index];
                break;
            case "-":
                numStack[index - 2] -= numStack[--index];
                break;
            case "*":
                numStack[index - 2] *= numStack[--index];
                break;
            case "/":
                numStack[index - 2] /= numStack[--index];
                break;
            default:
                // numStack[index++] = Integer.valueOf(s);
                //valueOf改为parseInt，减少自动拆箱装箱操作
                numStack[index++] = Integer.parseInt(s);
                break;
            }
        }
        return numStack[0];
    }
}
class Solution {
    // 栈实现   8 ms    36.7 MB    
    public static int evalRPN(String[] tokens) {
        Stack<Integer> numStack = new Stack<>();
        Integer op1, op2;
        for (String s : tokens) {
            switch (s) {
            case "+":
                op2 = numStack.pop();
                op1 = numStack.pop();
                numStack.push(op1 + op2);
                break;
            case "-":
                op2 = numStack.pop();
                op1 = numStack.pop();
                numStack.push(op1 - op2);
                break;
            case "*":
                op2 = numStack.pop();
                op1 = numStack.pop();
                numStack.push(op1 * op2);
                break;
            case "/":
                op2 = numStack.pop();
                op1 = numStack.pop();
                numStack.push(op1 / op2);
                break;
            default:
                numStack.push(Integer.valueOf(s));
                break;
            }
        }
        return numStack.pop();
    }
}

除自身以外数组的乘积

输入: [1,2,3,4]
输出: [24,12,8,6]
方法一：左右乘积列表
我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;

    // L 和 R 分别表示左右两侧的乘积列表
    int[] L = new int[length];
    int[] R = new int[length];

    int[] answer = new int[length];

    // L[i] 为索引 i 左侧所有元素的乘积
    // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
    L[0] = 1;
    for (int i = 1; i < length; i++) {
        L[i] = nums[i - 1] * L[i - 1];
    }

    // R[i] 为索引 i 右侧所有元素的乘积
    // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
    R[length - 1] = 1;
    for (int i = length - 2; i >= 0; i--) {
        R[i] = nums[i + 1] * R[i + 1];
    }

    // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
    for (int i = 0; i < length; i++) {
        answer[i] = L[i] * R[i];
    }

    return answer;
}
}
方法二：空间复杂度 
第一个循环应该是表示下三角中自上而下对每一行做连乘，而第二个循环是对上三角自下而上的连乘
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];

    // answer[i] 表示索引 i 左侧所有元素的乘积
    // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
    answer[0] = 1;
    for (int i = 1; i < length; i++) {
        answer[i] = nums[i - 1] * answer[i - 1];
    }

    // R 为右侧所有元素的乘积
    // 刚开始右边没有元素，所以 R = 1
    int R = 1;
    for (int i = length - 1; i >= 0; i--) {
        // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
        answer[i] = answer[i] * R;
        // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
        R *= nums[i];
    }
    return answer;
}
}

和为s的连续正数序列 （滑动窗口）

    窗口的左边界和右边界永远只能向右移动
    当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
    当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
什么是滑动窗口
滑动窗口可以看成数组中框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优的结果。
窗口的左边界和右边界永远只能向右移动
第一个问题，窗口何时扩大，何时缩小？
第二个问题，滑动窗口能找到全部的解吗？
当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
public int[][] findContinuousSequence(int target) {
    int i = 1; // 滑动窗口的左边界
    int j = 1; // 滑动窗口的右边界
    int sum = 0; // 滑动窗口中数字的和
    List<int[]> res = new ArrayList<>();

while (i <= target / 2) {
    if (sum < target) {
        // 右边界向右移动
        sum += j;
        j++;
    } else if (sum > target) {
        // 左边界向右移动
        sum -= i;
        i++;
    } else {
        // 记录结果
        int[] arr = new int[j-i];
        for (int k = i; k < j; k++) {
            arr[k-i] = k;
        }
        res.add(arr);
        // 左边界向右移动
        sum -= i;
        i++;
    }
}

return res.toArray(new int[res.size()][]);

}

滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
单调队列
我们先看什么是单调的双向队列，双向队列大家都知道，既能在头部进行插入、删除操作，也能在尾部进行插入删除操作，而所谓的单调，就是我们人为规定从队列的头部到尾部，所存储的元素是依次递减（或依次递增）的。如下所示：

也就是说，我们维护一个单调的双向队列，窗口在每次滑动的时候，我就从队列头部取当前窗口中的最大值，每次窗口新进来一个元素的时候，我就将它与队列中的元素进行大小比较：

如果刚刚进来的元素比队列的尾部元素大，那么先将队列尾部的元素弹出，然后把刚刚进来的元素添到队列的尾部；
如果刚刚进来的元素比队列的尾部元素小，那么把刚刚进来的元素直接添到队列的尾部即可。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k < 1 || nums.length < k) {
            return new int[0];
        }

    int index = 0;
    int[] res = new int[nums.length - k + 1];
    LinkedList<Integer> queue = new LinkedList<>();

    for (int i = 0; i < nums.length; i++) {
        // 在队列不为空的情况下，如果队列尾部的元素要比当前的元素小，或等于当前的元素
        // 那么为了维持从大到小的原则，我必须让尾部元素弹出
        while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
            queue.pollLast();
        }
        // 不走 while 的话，说明我们正常在队列尾部添加元素
        queue.addLast(i);
        // 如果滑动窗口已经略过了队列中头部的元素，则将头部元素弹出
        if (queue.peekFirst() == (i - k)) {
            queue.pollFirst();
        }
        // 看看窗口有没有形成，只有形成了大小为 k 的窗口，我才能收集窗口内的最大值
        if (i >= (k - 1)) {
            res[index++] = nums[queue.peekFirst()];
        }
    }
    return res;
}

}

将数组中所有 0 移动到数组末尾。

方法一：空间局部优化
class Solution {
    public void moveZeroes(int[] nums) {
        if(nums==null) {
            return;
        }
        //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
        int j = 0;
        for(int i=0;i<nums.length;++i) {
            if(nums[i]!=0) {
                nums[j++] = nums[i];
            }
        }
        //非0元素统计完了，剩下的都是0了
        //所以第二次遍历把末尾的元素都赋为0即可
        for(int i=j;i<nums.length;++i) {
            nums[i] = 0;
        }
    }
}    
方法二：空间最优，操作局部优化（双指针）
class Solution {
    public void moveZeroes(int[] nums) {
        if(nums==null) {
            return;
        }
        //两个指针i和j
        int j = 0;
        for(int i=0;i<nums.length;i++) {
            //当前元素!=0，就把其交换到左边，等于0的交换到右边
            if(nums[i]!=0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }
}

打乱数组

方法一： 暴力 【通过】
暴力算法简单的来说就是把每个数放在一个 ”帽子“ 里面，每次从 ”帽子“ 里面随机摸一个数出来
class Solution {
    private int[] array;
    private int[] original;

private Random rand = new Random();

private List<Integer> getArrayCopy() {
    List<Integer> asList = new ArrayList<Integer>();
    for (int i = 0; i < array.length; i++) {
        asList.add(array[i]);
    }
    return asList;
}

public Solution(int[] nums) {
    array = nums;
    original = nums.clone();
}

public int[] reset() {
    array = original;
    original = original.clone();
    return array;
}

public int[] shuffle() {
    List<Integer> aux = getArrayCopy();

    for (int i = 0; i < array.length; i++) {
        int removeIdx = rand.nextInt(aux.size());
        array[i] = aux.get(removeIdx);
        aux.remove(removeIdx);
    }

    return array;
}

}
方法二： Fisher-Yates 洗牌算法 【通过】
Fisher-Yates 洗牌算法跟暴力算法很像。在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换 - 这一步模拟了每次从 “帽子” 里面摸一个元素的过程，其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。

class Solution {
    private int[] array;
    private int[] original;

Random rand = new Random();

private int randRange(int min, int max) {
    return rand.nextInt(max - min) + min;
}

private void swapAt(int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public Solution(int[] nums) {
    array = nums;
    original = nums.clone();
}

public int[] reset() {
    array = original;
    original = original.clone();
    return original;
}

public int[] shuffle() {
    for (int i = 0; i < array.length; i++) {
        swapAt(i, randRange(i, array.length));
    }
    return array;
}
}

数组中的逆序对

public class Solution {

public int reversePairs(int[] nums) {
    int len = nums.length;

    if (len < 2) {
        return 0;
    }

    int[] copy = new int[len];
    for (int i = 0; i < len; i++) {
        copy[i] = nums[i];
    }

    int[] temp = new int[len];
    return reversePairs(copy, 0, len - 1, temp);
}

/**
 * nums[left..right] 计算逆序对个数并且排序
 *
 * @param nums
 * @param left
 * @param right
 * @param temp
 * @return
 */
private int reversePairs(int[] nums, int left, int right, int[] temp) {
    if (left == right) {
        return 0;
    }

    int mid = left + (right - left) / 2;
    int leftPairs = reversePairs(nums, left, mid, temp);
    int rightPairs = reversePairs(nums, mid + 1, right, temp);

    if (nums[mid] <= nums[mid + 1]) {
        return leftPairs + rightPairs;
    }

    int crossPairs = mergeAndCount(nums, left, mid, right, temp);
    return leftPairs + rightPairs + crossPairs;
}

/**
 * nums[left..mid] 有序，nums[mid + 1..right] 有序
 *
 * @param nums
 * @param left
 * @param mid
 * @param right
 * @param temp
 * @return
 */
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
    for (int i = left; i <= right; i++) {
        temp[i] = nums[i];
    }

    int i = left;
    int j = mid + 1;

    int count = 0;
    for (int k = left; k <= right; k++) {

        if (i == mid + 1) {
            nums[k] = temp[j];
            j++;
        } else if (j == right + 1) {
            nums[k] = temp[i];
            i++;
        } else if (temp[i] <= temp[j]) {
            nums[k] = temp[i];
            i++;
        } else {
            nums[k] = temp[j];
            j++;
            count += (mid - i + 1);
        }
    }
    return count;
}
}

最小的k个数

    用快排最最最高效解决 TopK 问题：
    大根堆(前 K 小) / 小根堆（前 K 大),Java中有现成的 PriorityQueue，实现起来最简单：
    二叉搜索树也可以 解决 TopK 问题哦
    数据范围有限时直接计数排序就行了：
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

private int[] quickSearch(int[] nums, int lo, int hi, int k) {
    // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
    int j = partition(nums, lo, hi);
    if (j == k) {
        return Arrays.copyOf(nums, j + 1);
    }
    // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
    return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
}

// 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
private int partition(int[] nums, int lo, int hi) {
    int v = nums[lo];
    int i = lo, j = hi + 1;
    while (true) {
        while (++i <= hi && nums[i] < v);
        while (--j >= lo && nums[j] > v);
        if (i >= j) {
            break;
        }
        int t = nums[j];
        nums[j] = nums[i];
        nums[i] = t;
    }
    nums[lo] = nums[j];
    nums[j] = v;
    return j;
}
}
我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
// 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
// 1. 若目前堆的大小小于K，将当前数字放入堆中。
// 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
//    反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }
        
        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}
二叉搜索树也可以 O(NlogK)解决 TopK 问题哦
与前两种方法相比，BST 有一个好处是求得的前K大的数字是有序的。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0 || arr.length == 0) {
        return new int[0];
    }
    // TreeMap的key是数字, value是该数字的个数。
    // cnt表示当前map总共存了多少个数字。
    TreeMap<Integer, Integer> map = new TreeMap<>();
    int cnt = 0;
    for (int num: arr) {
        // 1. 遍历数组，若当前map中的数字个数小于k，则map中当前数字对应个数+1
        if (cnt < k) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            cnt++;
            continue;
        } 
        // 2. 否则，取出map中最大的Key（即最大的数字), 判断当前数字与map中最大数字的大小关系：
        //    若当前数字比map中最大的数字还大，就直接忽略；
        //    若当前数字比map中最大的数字小，则将当前数字加入map中，并将map中的最大数字的个数-1。
        Map.Entry<Integer, Integer> entry = map.lastEntry();
        if (entry.getKey() > num) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (entry.getValue() == 1) {
                map.pollLastEntry();
            } else {
                map.put(entry.getKey(), entry.getValue() - 1);
            }
        }
    
}

    // 最后返回map中的元素
    int[] res = new int[k];
    int idx = 0;
    for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
        int freq = entry.getValue();
        while (freq-- > 0) {
            res[idx++] = entry.getKey();
        }
    }
    return res;
}
}
四、数据范围有限时直接计数排序就行了：
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 统计每个数字出现的次数
        int[] counter = new int[10001];
        for (int num: arr) {
            counter[num]++;
        }
        // 根据counter数组从头找出k个数作为返回结果
        int[] res = new int[k];
        int idx = 0;
        for (int num = 0; num < counter.length; num++) {
            while (counter[num]-- > 0 && idx < k) {
                res[idx++] = num;
            }
            if (idx == k) {
                break;
            }
        }
        return res;
    }
}

把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
    输入: [10,2]
    输出: "102"
    此题求拼接起来的 “最小数字” ，本质上是一个排序问题。
class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        fastSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    void fastSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        fastSort(strs, l, i - 1);
        fastSort(strs, i + 1, r);
    }
}
方法二：内置函数
public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) 
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }

二维数组

二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
    由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。

从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。

可以证明这种方法不会错过目标值。如果当前元素大于目标值，说明当前元素的下边的所有元素都一定大于目标值，因此往下查找不可能找到目标值，往左查找可能找到目标值。如果当前元素小于目标值，说明当前元素的左边的所有元素都一定小于目标值，因此往左查找不可能找到目标值，往下查找可能

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }
}

矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
    算法原理：
    深度优先搜索
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        char tmp = board[i][j];
        board[i][j] = '/';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = tmp;
        return res;
    }
}

机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
    本文选择使用广度优先搜索的方法来讲解。
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, m, n, k, visited);
    }
    public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        if(i >= m || j >= n || k < getSum(i) + getSum(j) || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited);
    }

private int getSum(int a) {
    int sum = a % 10;
    int tmp = a / 10;
    while(tmp > 0) {
        sum += tmp % 10;
        tmp /= 10;
    }
    return sum;
}

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
可以模拟打印矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，则顺时针旋转，进入下一个方向。
判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited，其中的每个元素
表示该位置是否被访问过。当一个元素被访问时，将 visited 中的对应位置的元素设为已访问。
如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数
量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回。
 public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int[] order = new int[total];
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order[i] = matrix[row][column];
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。
最直接的做法是将这个二维数组另存为为一维数组，并对该一维数组进行排序。最后这个一维数组中的第 k个数即为答案。
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int rows = matrix.length, columns = matrix[0].length;
        int[] sorted = new int[rows * columns];
        int index = 0;
        for (int[] row : matrix) {
            for (int num : row) {
                sorted[index++] = num;
            }
        }
        Arrays.sort(sorted);
        return sorted[k - 1];
    }
}
方法二：归并排序
这个矩阵的每一行均为一个有序数组。问题即转化为从这 n 个有序数组中找第 
k 大的数，可以想到利用归并排序的做法，归并到第 k 个数即可停止。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{matrix[i][0], i, 0});
        }
        for (int i = 0; i < k - 1; i++) {
            int[] now = pq.poll();
            if (now[2] != n - 1) {
                pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
            }
        }
        return pq.poll()[0];
    }
}
方法三：二分查找
那么矩阵中不大于 mid 的数，肯定全部分布在矩阵的左上角。
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(int[][] matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }
}

可以将矩阵看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素。
定义4个顶点的坐标位置left、right、top、bottom
1.从左到右遍历上侧元素， 当到达右顶点时停止
2.从上到下遍历右侧元素，当到达下右顶点时停止
3.从右向左侧遍历
4.从下向上遍历
遍历完毕后，四个顶点位置进行内缩
left和top分别加一
right和bottom分别减一，然后再遍历，直到遍历完所有元素为止。
 public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[] order = new int[rows * columns];
        int index = 0;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order[index++] = matrix[top][column];
            }
            for (int row = top + 1; row <= bottom; row++) {
                order[index++] = matrix[row][right];
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order[index++] = matrix[bottom][column];
                }
                for (int row = bottom; row > top; row--) {
                    order[index++] = matrix[row][left];
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。

该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
方法一：暴力法
方法二：二分法搜索
class Solution {
    private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].length-1 : matrix.length-1;

    while (hi >= lo) {
        int mid = (lo + hi)/2;
        if (vertical) { // searching a column
            if (matrix[start][mid] < target) {
                lo = mid + 1;
            } else if (matrix[start][mid] > target) {
                hi = mid - 1;
            } else {
                return true;
            }
        } else { // searching a row
            if (matrix[mid][start] < target) {
                lo = mid + 1;
            } else if (matrix[mid][start] > target) {
                hi = mid - 1;
            } else {
                return true;
            }
        }
    }

    return false;
}

public boolean searchMatrix(int[][] matrix, int target) {
    // an empty matrix obviously does not contain `target`
    if (matrix == null || matrix.length == 0) {
        return false;
    }

    // iterate over matrix diagonals
    int shorterDim = Math.min(matrix.length, matrix[0].length);
    for (int i = 0; i < shorterDim; i++) {
        boolean verticalFound = binarySearch(matrix, target, i, true);
        boolean horizontalFound = binarySearch(matrix, target, i, false);
        if (verticalFound || horizontalFound) {
            return true;
        }
    }
    
    return false; 
}
}
方法三修剪矩阵
首先，我们初始化一个指向矩阵左下角的 
(row，col) 指针。然后，直到找到目标并返回 true（或者指针指向矩阵维度之外的 
(row，col) 为止，我们执行以下操作：如果当前指向的值大于目标值，则可以 “向上” 移动一行。 否则，如果当前指向的值小于目标值，则可以移动一列。不难理解为什么这样做永远不会删减正确的答案；因为行是从左到右排序的，所以我们知道当前值右侧的每个值都较大。 因此，如果当前值已经大于目标值，我们知道它右边的每个值会比较大。也可以对列进行非常类似的论证，因此这种搜索方式将始终在矩阵中找到目标（如果存在）。
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // start our "pointer" in the bottom-left
        int row = matrix.length-1;
        int col = 0;

    while (row >= 0 && col < matrix[0].length) {
        if (matrix[row][col] > target) {
            row--;
        } else if (matrix[row][col] < target) {
            col++;
        } else { // found it
            return true;
        }
    }

    return false;
}
}