记录刷过的算法题

记录自己刷过的算法题,通过之后得出最佳算法答案


数组查询

  • 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    1
    2
    3
    4
    5
    6
    int len = nums.length;
    int result=0;
    for(int i=0;i<len;i++){
    result ^= nums[i];
    }
    return result;

    ⚠️注意:相同数据 ^= 运算之后结果为0, 如果 result=0; 那么 result ^= num,result = num;

  • 假设淘宝一天有5亿条成交数据,求出销量最高的100个商品并给出算法的时间复杂度?

    1
    解决:将所有的记录分开成若干个小部分,对于每个小部分选出100个最高的商品,然后两两归并,取前100个。

排序算法

排序方法 平均时间复杂度 最好情况下的时间复杂度 最坏情况下的时间复杂度 空间复杂度(辅助存储) 稳定性
直接插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(n^1.5) O(n) O(n^2) O(1) 不稳定
直接选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
堆排序 O(nlog2(n)) O(nlog2(n)) O(nlog2(n)) O(1) 不稳定
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
快速排序 O(nlog2(n)) O(nlog2(n)) O(nlog2(n)) O(nlog2(n)) 不稳定
归并排序 O(nlog2(n)) O(nlog2(n)) O(nlog2(n)) O(1) 稳定
———————

直接插入排序

1
原理:它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 插入排序在实现上,通常采用in-place排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
1
2
3
4
5
6
7
8
9
10
11
public static void sort(int[] numbers){
for (int i = 1; i < numbers.length; i++) {
int currentNumber = numbers[i];
int j = i - 1;
while (j >= 0 && numbers[j] > currentNumber) {
numbers[j + 1] = numbers[j];
j--;
}
numbers[j + 1] = currentNumber;
}
}

希尔排序

1
原理:希尔排序实质是分组插入排序,基本思想是希尔排序是将待排序的数组元素 按下标的一定增量分组 ,分成多个子序列,然后对各个子序列进行直接插入排序算法排序;然后依次缩减增量再进行排序,直到增量为1时,进行最后一次直接插入排序,排序结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 希尔排序
* @param arrays 需要排序的序列
*/
public static void sort(int[] arrays){
if(arrays == null || arrays.length <= 1){
return;
}
//增量
int incrementNum = arrays.length/2;
while(incrementNum >=1){
for(int i=0;i<arrays.length;i++){
//进行插入排序
for(int j=i;j<arrays.length-incrementNum;j=j+incrementNum){
if(arrays[j]>arrays[j+incrementNum]){
int temple = arrays[j];
arrays[j] = arrays[j+incrementNum];
arrays[j+incrementNum] = temple;
}
}
}
//设置新的增量
incrementNum = incrementNum/2;
}
}

直接选择排序

1
原理:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,知道进行比较的记录只剩下一个为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void selectSort(int[] a) {
if (a == null || a.length <= 0) {
return;
}
for (int i = 0; i < a.length; i++) {
int temp = a[i];
int flag = i; // 将当前下标定义为最小值下标
for (int j = i + 1; j < a.length; j++) {
if (a[j] < temp) {// a[j] < temp 从小到大排序;a[j] > temp 从大到小排序
temp = a[j];
flag = j; // 如果有小于当前最小值的关键字将此关键字的下标赋值给flag
}
}
if (flag != i) {
a[flag] = a[i];
a[i] = temp;
}
}
}

堆排序

1
2
3
原理:堆排序就是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是,将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的 n-1 个序列重新构造成一个堆,这样就会得到 n 个元素中次大的值。如此反复执行,便能得到一个有序序列了。 堆排序的实现需要解决的两个关键问题: 
1. 将一个无序序列构成一个堆。
2. 输出堆顶元素后,调整剩余元素成为一个新堆。
1
2
3
4
5
6
7
8
9
10
11
//堆排序
public int[] heapSort(int[] array){
array = buildMaxHeap(array); //初始建堆,array[0]为第一趟值最大的元素
for(int i=array.length-1;i>1;i--){
int temp = array[0]; //将堆顶元素和堆低元素交换,即得到当前最大元素正确的排序位置
array[0] = array[i];
array[i] = temp;
adjustDownToUp(array, 0,i); //整理,将剩余的元素整理成堆
}
return array;
}

冒泡排序

1
原理:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。重复第一趟步骤,直至全部排序完成。
1
2
3
4
5
6
7
8
9
10
11
public static void BubbleSort(int[] arr) {
int temp;//定义一个临时变量
for(int i=0;i<arr.length-1;i++){//冒泡趟数
for(int j=0;j<arr.length-i-1;j++){
if(arr[j+1]<arr[j]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

快速排序

1
原理:快速排序也是分治法思想的一种实现,他的思路是使数组中的每个元素与基准值(Pivot,通常是数组的首个值,A[0])比较,数组中比基准值小的放在基准值的左边,形成左部;大的放在右边,形成右部;接下来将左部和右部分别递归地执行上面的过程:选基准值,小的放在左边,大的放在右边。直到排序结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void quickSort(int[] nums, int low, int height) {
if (low > height) {
return;
}
int i = low;
int j = height;
int key = nums[low];
while (i < j) {
while (i < j && nums[j] > key) {
j --;
}
while (i < j && nums[i] <= key) {
i ++;
}
if (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
int temp = nums[low];
nums[low] = nums[i];
nums[i] = temp;
quickSort(nums, low, i - 1);
quickSort(nums, i + 1, height);
}

归并排序

1
2
3
4
归并排序的原理大致可分为三步: 
1. 分解:把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素
2. 治理:对每个子序列分别调用归并排序MergeSort, 进行递归操作
3. 合并:合并两个排好序的子序列,生成排序结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public void sort(int[] nums, int low, int height) {
int mid = (low + height) / 2;
if (low < height) {
sort(nums, low, mid);
sort(nums, mid + 1, height);
merge(nums, low, mid, height);
}
}

private void merge(int[] nums, int low, int mid, int height) {
int[] temp = new int[height - low + 1];
int i = low;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= height) {
if(nums[i] < nums[j]) {
temp[index ++] = nums[i ++];
} else {
temp[index ++] = nums[j ++];
}
}
while (i <= mid) {
temp[index ++] = nums[i ++];
}
while (j <= height) {
temp[index ++] = nums[j ++];
}
for (int n = 0; n < temp.length; n ++) {
nums[low + n] = temp[n];
}
}

计算斐波那契数

1
2
3
4
5
int fibonacci(int n) {
if (n == 0 || n == 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
var result = fibonacci(20);