标签：return offer int list 算法 array 排序 public size
摘要
一、排序算法原理与解题方法
二、排序算法练习题目
2.1 数组中重复的数字
数组中重复的数字_牛客题霸_牛客网
package 排序算法;
import java.util.ArrayList;
/**
* @Classname JZ3数组中重复的数字
* @Description TODO
* @Date 2022/2/4 9:20
* @Created by xjl
*/
public class JZ3数组中重复的数字 {
/**
* @description 利用Hashmap的相关原理 list等相关原理 O(n)
*
* 或者是的采用的数组的排序 然后遍历一遍但是的最小的是nlog(n)
* @param: numbers
* @date: 2022/2/4 9:20
* @return: int
* @author: xjl
*/
public int duplicate (int[] numbers) {
ArrayList<Integer> list=new ArrayList<>();
for (int i:numbers){
if (!list.contains(i)){
list.add(i);
}else {
return i;
}
}
return -1;
}
}
2.2 数组中的逆序对
数组中的逆序对_牛客题霸_牛客网
package 排序算法;
/**
* @Classname JZ51数组中的逆序对
* @Description TODO
* @Date 2022/2/4 9:45
* @Created by xjl
*/
public class JZ51数组中的逆序对 {
/**
* @description 采用的 双遍历 但是复杂度是O(n^2)
* <p>
* 时间复杂度要求的在nlog(n) 想到的是归并排序
* @param: array
* @date: 2022/2/4 9:46
* @return: int
* @author: xjl
*/
int count = 0;
public int InversePairs(int[] array) {
// 长度小于2则无逆序对
if (array.length < 2) {
return 0;
}
// 进入归并
mergeSort(array, 0, array.length - 1);
return count;
}
private void mergeSort(int[] array, int left, int right) {
// 找分割点
int mid = (left + right) >> 1;
if (left < right) {
// 左子数组
mergeSort(array, left, mid);
// 右子数组
mergeSort(array, mid + 1, right);
// 并
merge(array, left, mid, right);
}
}
private void merge(int[] array, int left, int mid, int right) {
// 创建临时数组，长度为此时两个子数组加起来的长度
int[] arr = new int[right - left + 1];
// 临时数组的下标起点
int index = 0;
// 保存在原数组的起点下标值
int s = left;
// 左子数组的起始指针
int l = left;
// 右子数组的起始指针
int r = mid + 1;
while (l <= mid && r <= right) {
// 当左子数组的当前元素小的时候，跳过，无逆序对
if (array[l] <= array[r]) {
// 放入临时数组
arr[index] = array[l];
// 临时数组下标+1
index++;
// 左子数组指针右移
l++;
} else { // 否则，此时存在逆序对
// 放入临时数组
arr[index] = array[r];
// 逆序对的个数为 左子数组的终点- 当前左子数组的当前指针
count += mid - l + 1;
count %= 1000000007;
// 临时数组+1
index++;
// 右子数组的指针右移
r++;
}
}
// 左子数组还有元素时，全部放入临时数组
while (l <= mid)
arr[index++] = array[l++];
// 右子数组还有元素时，全部放入临时数组
while (r <= right)
arr[index++] = array[r++];
// 将临时数组中的元素放入到原数组的指定位置
for (int num : arr) {
array[s++] = num;
}
}
}
2.3 最小的K个数
最小的K个数_牛客题霸_牛客网
package 排序算法;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* @Classname JZ40最小的K个数
* @Description TODO
* @Date 2022/2/4 10:48
* @Created by xjl
*/
public class JZ40最小的K个数 {
/**
* @description 可以采用的归并的排序的原理 然后取前k个
* @param: input
* @param: k
* @date: 2022/2/4 10:48
* @return: java.util.ArrayList<java.lang.Integer>
* @author: xjl
*/
ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
if (input.length == 0 || input.length < k || k == 0) {
return new ArrayList<>();
}
merge_sort(input, 0, input.length - 1);
int index = 0;
while (k > 0) {
list.add(input[index++]);
k--;
}
return list;
}
private void merge_sort(int[] array, int left, int right) {
int mid = (left + right) >> 1;
if (left < right) {
merge_sort(array, left, mid);
merge_sort(array, mid + 1, right);
merge(array, left, mid, right);
}
}
private void merge(int[] array, int left, int mid, int right) {
int[] arr = new int[right - left + 1];
int index = 0;
int s = left;
int l = left;
int r = mid + 1;
while (l <= mid && r <= right) {
if (array[l] <= array[r]) {
arr[index++] = array[l++];
} else {
arr[index++] = array[r++];
}
}
while (l <= mid) {
arr[index++] = array[l++];
}
while (r <= right) {
arr[index++] = array[r++];
}
for (int i : arr) {
array[s++] = i;
}
}
/**
* @description 使用优先队列的结果来判断
* @param: input
* @param: k
* @date: 2022/2/4 11:18
* @return: java.util.ArrayList<java.lang.Integer>
* @author: xjl
*/
public ArrayList<Integer> GetLeastNumbers_Solution2(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if (input.length == 0 || input.length < k || k == 0) {
return list;
}
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
for (int i : input) {
queue.add(i);
}
while (k > 0) {
list.add(queue.poll());
k--;
}
return list;
}
@Test
public void test() {
int[] array = {4, 5, 1, 6, 2, 7, 3, 8};
int k = 4;
ArrayList<Integer> list = GetLeastNumbers_Solution(array, k);
System.out.println(list);
}
}
2.4 数据流中的中位数
数据流中的中位数_牛客题霸_牛客网
package 排序算法;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
/**
* @Classname JZ41数据流中的中位数
* @Description TODO
* @Date 2022/2/4 13:53
* @Created by xjl
*/
public class JZ41数据流中的中位数 {
ArrayList<Integer> list = new ArrayList<>();
public void Insert(Integer num) {
list.add(num);
}
public Double GetMedian() {
Collections.sort(list);
if (list.size() % 2 != 0) {
return Double.valueOf(list.get(list.size() / 2));
} else {
return Double.valueOf((list.get(list.size() / 2) + list.get(list.size() / 2 - 1)) / 2);
}
}
//堆
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
private PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
public void Insert1(Integer num) {
if (maxHeap.isEmpty() || num < maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
if (maxHeap.size() == minHeap.size() + 2) {
minHeap.add(maxHeap.poll());
}
if (minHeap.size() == maxHeap.size() + 2) {
maxHeap.add(minHeap.poll());
}
}
public Double GetMedian1() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.size() > minHeap.size() ? (double) maxHeap.peek() : (double) minHeap.peek();
}
}
public void Insert2(Integer num) {
int index = list.size();
for (int i = 0; i < index; ++i) {
if (list.get(i) > num) {
index = i;
}
}
list.add(index, num);
}
public Double GetMedian2() {
int len = list.size();
if (len == 0) {
return null;
}
int i = len / 2;
if (len % 2 == 0) {
return (double) (list.get(i) + list.get(i - 1)) / 2;
} else {
return (double) list.get(i);
}
}
//堆
public PriorityQueue<Integer> maxHeap1 = new PriorityQueue<>((o1, o2) -> o2 - o1);
public PriorityQueue<Integer> minHeap1 = new PriorityQueue<>((o1, o2) -> o1 - o2);
int count = 0;
public void insert(Integer num) {
//偶数放入小顶堆
if (count % 2 != 0) {
// 如果插入的数字比大顶堆元素小
if (!maxHeap1.isEmpty() && maxHeap1.peek() > num) {
int oldmax = maxHeap1.poll();
maxHeap1.add(num);
num = oldmax;
}
minHeap1.add(num);
} else {
if (!minHeap1.isEmpty() && minHeap1.peek() < num) {
int oldmin = minHeap1.poll();
minHeap1.add(num);
num = oldmin;
}
maxHeap1.add(num);
}
count++;
}
public Double Get() {
int size = minHeap1.size() + maxHeap1.size();
if (size == 0) {
return 0.0;
}
if (size % 2 == 0) {
return (minHeap1.peek()+maxHeap1.peek())/2.0;
}else {
return Double.valueOf(maxHeap1.peek());
}
}
@Test
public void test() {
int[] array = {5, 2, 3, 4, 1, 6, 7, 0, 8};
for (int i : array) {
//Insert2(i);
}
ArrayList<Integer> list1=new ArrayList<>();
list1.add(0);
list1.add(1,5);
list1.add(0,3);
list1.add(2,6);
System.out.println(list1);
}
}
博文参考
标签：return,
offer,
int,
list,
算法,
array,
排序,
public,
size
From： https://blog.51cto.com/u_13643065/6168621