剑指offer排序专题

剑指offer排序专题

jz3 数组中重复的数字描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤n≤10000

进阶：时间复杂度 O(n) ，空间复杂度 O(n)

数组中重复的数字_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numbers int整型一维数组 * @return int整型*/public int duplicate (int[] numbers) {// write code hereint s[] = new int[10005];for(int i = 0; i < numbers.length; i++){s[numbers[i]] += 1;if(s[numbers[i]] >= 2) return numbers[i];}return -1;}
}

桶排序，如果一个数出现两次则其对应下标的数组的值大于等于2

JZ51 数组中的逆序对描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

数据范围： 对于 50% 的数据,size<=10_e4
对于 100% 的数据, size≤10_e5

数组中所有数字的值满足 0≤val≤10_e9

要求：空间复杂度 O(n)，时间复杂度 O(*nlogn)

题目保证输入的数组中没有的相同的数字

数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)

public class Solution {private int P = 1000000007;public int InversePairs(int [] array) {long ans = merge_sort(array, 0, array.length - 1) % P;return (int)ans;}public long merge_sort(int[] arr, int left,int right) {if (left >= right) return 0;int mid = (left + right) >> 1;long res = merge_sort(arr,left,mid) + merge_sort(arr,mid + 1, right) % P;int[] temp = new int[right - left + 1];int idx = 0;int i = left;int j = mid + 1;while(i <= mid && j <= right){if(arr[i] <= arr[j]){temp[idx++] = arr[i++];}else {res += mid - i + 1;temp[idx++] = arr[j++];}}while(i <= mid){temp[idx++] = arr[i++];}while(j <= right){temp[idx++] = arr[j++];}for(int k = 0; k < idx; k++){arr[left + k] = temp[k]; }return res;}
}

简单的逆序对板子题

JZ40 最小的K个数描述

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000

要求：空间复杂度 O(n) ，时间复杂度 O(nlogk)

最小的K个数_牛客题霸_牛客网 (nowcoder.com)

import java.util.ArrayList;
import java.util.*;
public class Solution {public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {ArrayList<Integer> ans = new ArrayList<>();if(k == 0 || input.length == 0) return ans;Sort(input,0,input.length - 1,k);for(int i = 0; i < k; i++){ans.add(input[i]);}  return ans;    }private int Sort(int[] arr,int left,int right,int k){if(left >= right) return arr[left];int i = left - 1;int j = right + 1;int x = arr[(left + right) >> 1];while(i < j){do{i++;}while(arr[i] < x);do{j--;}while(arr[j] > x);if(i < j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int sl = j - left + 1;if(sl >= k) return Sort(arr,left,j,k);return Sort(arr,j + 1,right,k - sl);}
}

快速排序，板子题

JZ41 数据流中的中位数描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

数据范围：数据流中数个数满足 1≤n≤1000 ，大小满足 1≤val≤1000

进阶： 空间复杂度 O(n) ， 时间复杂度 O(nlogn)

数据流中的中位数_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;
public class Solution {private List<Integer> heap = new LinkedList<Integer>();public void Insert(Integer num) {if(heap.size() == 0){heap.add(num);}else{int i = 0;for(; i < heap.size(); i++){if(heap.get(i) >= num) {break;}} heap.add(i,num);}}public Double GetMedian() {int n = heap.size();if((n % 2) == 1){return (double)heap.get(n / 2);}else {return ((double)heap.get(n / 2) + (double)heap.get((n / 2 - 1)))/2;}}}

开一个底层为链表的集合，每次插入时按顺序保持数据有序，求平均数时奇数取中心（n / 2），偶数取两数平均 ((n / 2) + (n / 2 - 1)) / 2, 切记要是double防止精度丢失。