公司建设网站费用属于什么费用,南平网站建设,wordpress 注册钩子,北京全网推广剑指offer排序专题
jz3 数组中重复的数字描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的#xff0c;但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如#xff0c;如果输入长度为7的数组[…剑指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% 的数据,size10e4 对于 100% 的数据, size≤10e5
数组中所有数字的值满足 0≤val≤10e9
要求空间复杂度 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 ArrayListInteger GetLeastNumbers_Solution(int [] input, int k) {ArrayListInteger 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 ListInteger heap new LinkedListInteger();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防止精度丢失。
