自己电脑如何做网站服务器,南昌网站seo技术厂家,广州网页设计薪酬,网站建设是什么专业啊文章目录 数组中重复的数字题目思路代码实现中等难度思路代码实现 数组中的逆序对题目思路代码实现 最小K个数思路代码实现 数据流中的中位数题目思路代码实现 数组中重复的数字
题目
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的#xff0… 文章目录 数组中重复的数字题目思路代码实现中等难度思路代码实现 数组中的逆序对题目思路代码实现 最小K个数思路代码实现 数据流中的中位数题目思路代码实现 数组中重复的数字
题目
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如如果输入长度为7的数组[2,3,1,0,2,5,3]那么对应的输出是2或者3。存在不合法的输入的话输出-1
思路
使用HashSet的性质进行判断处理即可
代码实现
public int duplicate (int[] numbers) {if(numbers null || numbers.length 0){return -1;}HashSetInteger hashSet new HashSet();for(int num:numbers){if(hashSet.contains(num)){return num;}else{hashSet.add(num);}}return -1;}中等难度
给你一个长度为 n 的整数数组 nums 其中 nums 的所有整数都在范围 [1, n] 内且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数并以数组形式返回。 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。 LeetCode链接
思路
由于nums数组中的数字范围为[1-n],则我们可以将对应数字放在其对应下标位置[0~n-1]这样如果存在数字重复则一定会有num[i]-1!index存在,这样就可以找出重复数字。
代码实现 public ListInteger findDuplicates(int[] nums) {ListInteger result new ArrayList();for(int i 0; i nums.length;i){while(nums[i] ! nums[nums[i]-1]){swap(i,nums[i]-1,nums);}}for(int i 0; i nums.length;i){if(nums[i] - 1 !i){result.add(nums[i]);}}return result;}private void swap(int i,int j, int[] nums){int temp nums[i];nums[i] nums[j];nums[j] temp;}数组中的逆序对
题目
在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007 牛客题目链接
思路
采用归并排序思想解决
代码实现 private int result;/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * return int整型*/public int InversePairs (int[] nums) {if(nums null || nums.length 0){return 0;}mergeSort(nums,0,nums.length-1);return result ;}private void mergeSort(int[] nums,int l,int r){int mid l (r - l) /2;if(l r){mergeSort(nums,l,mid);mergeSort(nums,mid1,r);merge(nums,l,mid,r);}}private void merge(int[] nums,int l,int mid,int r){int[] help new int[r-l1];int i 0;int p1 l;int p2 mid 1 ;while(p1 mid p2 r){if(nums[p1] nums[p2]){help[i] nums[p1];}else {resultmid - p11;result% 1000000007;help[i] nums[p2];}}while(p1 mid){help[i] nums[p1];}while(p2 r){help[i] nums[p2];}for(int j 0;j help.length;j){nums[lj] help[j];}}最小K个数
设计一个算法找出数组中最小的k个数。以任意顺序返回这k个数均可。 示例 输入 arr [1,3,5,7,2,4,6,8], k 4 输出 [1,2,3,4] LeetCode链接
思路
方法1 对数组整体进行排序然后取前k个数这种方式比较简单就不再过多赘述对应时间复杂度为O(nlogn)方法2
定义大根堆Java中对应的就是优先级队列将数组中前k个数丢入大根堆中然后遍历[k,arr.length-1]位置数据每次与大根堆堆顶元素即队列中最大数进行比较如果比最大数小则堆顶元素出队新的元素入队最终会产生新的最小元素对应时间复杂度为O(nlogk);
代码实现
这里采用大根堆的思路来解决问题 public int[] smallestK(int[] arr, int k) {if(arr null || arr.length k){return new int[0];}if(k 0){return new int[0];}PriorityQueueInteger queue new PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});int[] result new int[k];for(int i 0 ; i k ; i){queue.offer(arr[i]);}for(int i k ; i arr.length;i){int peek queue.peek();if(arr[i] peek){queue.poll();queue.offer(arr[i]);}}int j 0;while(!queue.isEmpty()){int num queue.poll();result[j] num;}return result;}数据流中的中位数
题目
中位数 是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。 例如 [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 3) / 2 2.5 设计一个支持以下两种操作的数据结构
void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。 LeetCode链接
思路
定义一个大顶堆和小顶堆当大顶堆没有元素时先放入大顶堆中如果添加的元素小于等于大顶堆堆顶元素直接放入大顶堆中否则放入小顶堆中保证大顶堆中都是较小的一半元素小顶堆中是较大的一半元素同时当两个堆中元素数量相差为2时将元素多的堆顶元素放入元素少的堆中保证两个堆元素数之差在1以内此时取中位数即两种情况 a. 两个堆中元素数量相等直接取堆顶元素相加 /2 b.两个堆中元素数量不相等则中位数为数量多的堆顶元素 更多详细思路可参考Java 贪心算法经典问题解决
代码实现 //Java优先级队列 默认小顶堆private PriorityQueueInteger minQueue new PriorityQueue();// 定义大顶堆private PriorityQueueInteger maxQueue new PriorityQueue((x,y) - (y-x));public MedianFinder() {}//加入元素时public void addNum(int num) {if(maxQueue.size() 0){maxQueue.offer(num);} else {int peekNum maxQueue.peek();if(peekNum num){maxQueue.offer(num);}else{minQueue.offer(num);}changeQueueSize();}}public double findMedian() {int maxSize maxQueue.size();if(maxSize 0){return 0;}int minSize minQueue.size();if(minSize maxSize){return (maxQueue.peek() minQueue.peek()) / 2.0;}double result maxSize minSize ? maxQueue.peek(): minQueue.peek();return result;}private void changeQueueSize(){int maxSize maxQueue.size();int minSize minQueue.size();if(maxSize - minSize 2){minQueue.offer(maxQueue.poll());}if(minSize - maxSize 2){maxQueue.offer(minQueue.poll());}}
