2024-03-02 20:28:08
第一天
- 时间复杂度
- 常数操作(和数据量无关)
加减乘除属于常数操作
数组中提取数据属于常数操作
- 非常数操作(和数据量有关)
- 从链表中提取数据不属常数操做
排序方法
选择排序
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public static void buttonSort(int[] arr){
if ( arr == null || arr.length<2){
return;
}
for ( int s = arr.length - 1 ;s >0;s--){
for ( int f = 0 ; f < arr.length ;f++){
if (arr[f] > arr [f+1]){
swap(arr, f ,f + 1);
}
}
}
}
public static void swap (int[] arr, int i1 ,int i2){
arr[i1] = arr[i1] ^ arr[i2];
arr[i2] = arr[i1] ^ arr[i2];
arr[i1] = arr[i1] ^ arr[i2];
}异或运算 (不同为1,相同为0)(无进位相加)
1
2
3
4
5
6public static void swap(int a,int b);
a= a^b;
b= a^b;
a =a^b;
//aba或者bab都可以交换两个数的值
//只有a,b两个值的存储位置不同才可以这么计算- 例题
一个数组中有的数存在奇数次有的数存在偶数次怎么快速找出存在次数为奇数的数(注:奇数仅有一个)(注:奇数有两个的解决方法)1
2
3
4
5
6
7public static void printOddTimesNums(int[] arr){
int eor = 0;
for (int i = 0 ; i< arr.length;i++){
eor ^= arr[i];
}
System.out.println("eor");
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public static void printOddTimesNums(int[] arr){
int eor = 0;
for (int i = 0 ; i< arr.length;i++){
eor ^= arr[i];
}
//eor = a^b
// eor !=0
int a = eor & (~eor +1);
//取eor最👉边为1赋值给a
int onlyOne = 0;
for (int cur : arr){
if ((a & cur) != 0){
//注意这里不可以(a&cur) == 1 因为==1只有在最后一位都为一才会等于1这里面可能不是在最后一位上等于1 可能在其他位上同时等于1 但是 == 0 是可以的
onlyOne ^= cur ;
}
}
System.out.println(onlyOne +"第二个数是" +(eor^onlyOne));
}
public static void main(String[] args) {
test sum = new test();
int[] arr = {2,2,3,3,4,4,5,5,5,6,6,7,7,7,8,8};
sum.printOddTimesNums(arr);
}
//输出结果为
- 例题
插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--) {
swap(arr, j, j+1);
}
}
}
public static void swap(int arr[], int fir, int sec) {
arr[fir] = arr[fir] ^ arr[sec];
arr[sec] = arr[fir] ^ arr[sec];
arr[fir] = arr[fir] ^ arr[sec];
}
public static void main(String[] args) {
test sort = new test();
int[] arr1 = {1, 5, 3, 6,4,7,3,6,2,7};
sort.insertSort(arr1);
for (int i = 0; i < arr1.length; i++) {
System.out.println(arr1[i]);
}
}合并排序(2024 3 14)
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50public class mergeSort{
public int[] getSort(int[] arr){
return process( arr,0,arr.length-1);
}
public int[] process(int[] arr,int L ,int R){
if (L==R){
return arr;
}
int mid = (L+((R-L)>>1));
process(arr,L,mid);
process(arr,mid+1,R);
merge(arr , L, mid , R);
return arr;
}
public int[] merge(int[] arr,int L,int mid,int R){
int[] help = new int[R-L+1];
int i = 0;
int left = L;
int right = mid +1 ;
while(left<=mid && right<=R){
help[i++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
}
while(left <= mid){
help[i++] = arr[left++];
}
while(right<=R){
help[i++] = arr[right++];
}
for(int a = 0; a< help.length;a++){
arr[L+a] = help[a];
}
return arr;
}
public int[] randomArray(int maxValue , int maxSize){
int[] arr = new int[(int)(Math.random()*maxSize)] ;
for (int i =0 ; i<arr.length;i++){
arr[i] =((int)(Math.random()*(maxValue+1))-(int)(Math.random()*maxValue));
}
return arr;
}
public static void main (String[] args){
mergeSort new1 = new mergeSort();
int[] arr = new1.randomArray(100,100);
new1.getSort(arr);
for (int a =0 ;a< arr.length;a++){
System.out.println(arr[a]);
}
}
}合并排序下如何求smallSum (2024 3 15) (战斗爽!!!!)
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57public class samllSum {
public int smallSum(int[] arr){
if(arr == null || arr.length<2){
return 0;
}
return process( arr,0,arr.length-1);
}
public int process(int[] arr,int L ,int R){
if (L==R){
return 0;
}
int mid = (L+((R-L)>>1));
return process(arr, L, mid) + process(arr, mid + 1, R) + merge(arr, L, mid, R);
}
public int merge(int[] arr,int L,int mid,int R){
int[] help = new int[R-L+1];
int i = 0;
int left = L;
int right = mid +1 ;
int smallSum =0;
while(left<=mid && right<=R){
smallSum += arr[left] < arr[right] ? arr[left] * (R-right+1) : 0;
// System.out.println(smallSum);
help[i++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
}
while(left <= mid){
help[i++] = arr[left++];
}
while(right<=R){
help[i++] = arr[right++];
}
for(int a = 0; a< help.length;a++){
arr[L+a] = help[a];
}
return smallSum;
}
public int[] randomArray(int maxValue , int maxSize){
int[] arr = new int[(int)(Math.random()*maxSize)] ;
for (int i =0 ; i<arr.length;i++){
arr[i] =((int)(Math.random()*(maxValue+1))-(int)(Math.random()*maxValue));
}
return arr;
}
public static void main (String[] args){
samllSum new1 = new samllSum();
int[] arr = new1.randomArray(100,100);
// int[] arr = { 1,3,4,2,5};
System.out.println("注意这里是分割线");
System.out.println("smallSum的值为"+ new1.smallSum(arr) );
new1.smallSum(arr);
for (int a =0 ;a< arr.length;a++){
System.out.println(arr[a]);
}
}
}
2024 3 10
- 如何在一堆数中找到最大值
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
32
33
34
35public class dataalg{
private int max;
public int getMax(int[] arr){
return process(arr,0 , arr.length - 1);
}
public int process(int[] arr ,int L ,int R){
if (L == R){
return arr[L];
}
int mid = L +( ((R - L))>>1);
int leftMax = process(arr,L,mid);
int rightMax = process(arr,mid + 1, R);
max = Math.max(leftMax,rightMax);
return max;
}
public void printMaxz(){
System.out.println(max);
}
public int[] randomCountGenerate (int maxSize ,int maxValue){
int[] arr = new int[(int)(Math.random() * maxSize)];
for ( int i = 0; i<arr.length;i++){
arr[i] =(int)(Math.random()*(maxValue+1)) - ((int)(Math.random() * maxValue));
}
return arr;
}
public static void main(String[] args){
dataalg data = new dataalg();
int[] arr = data. randomCountGenerate(100,100);
data.getMax(arr);
data.printMaxz();
for (int i =0 ;i<arr.length;i++){
System.out.println(arr[i]+" ,");
}
}
}
2024 3 14
- 关于时间复杂度的比较
-mster公式
T(N) = a*T($\frac{N}{b}$)+O($N^d$)- $$ \log_b a < d $$
则时间复杂度为 O($ N^d $) - $$ \log_b a > d $$
则时间复杂度为 O($N^{\log_b a}$) - $$ \log_b a = d $$
则时间复杂度为 O($N^d * \log_N$)
- $$ \log_b a < d $$
- 关于时间复杂度的比较
#字棋
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102public class heapify {
public static void main(String args[]){
final int SIZE =3;
int[][] a = new int[SIZE][SIZE];
Scanner in = new Scanner(System.in);
int numofx = 0;
int numofo = 0;
boolean result = false;
for (int i =0 ;i<3;i++){
for (int j =0;j<3;j++){
a[i][j]=in.nextInt();
System.out.println("THE:("+(i+1)+","+(j+1)+")");
}
}
numofo =0;
numofx =0;
for (int i1=0;i1<3;i1++){
for(int i2 =0;i2<3;i2++){
if (i1+i2==2 && a[i1][i2]==1){
numofx++;
if (numofx==3){
System.out.println("X1 WIN THE GAME");
break;
}
}
if (i1+i2==2 && a[i1][i2]==0){
numofo++;
if (numofo==3){
System.out.println("O1 WIN THE GAME");
break;
}
}
}
}
numofo =0;
numofx =0;
for (int i1=0;i1<3;i1++){
for(int i2 =0;i2<3;i2++){
if (i1==i2 && a[i1][i2]==1){
numofx++;
if (numofx==3){
System.out.println("X2 WIN THE GAME");
break;
}
}
if (i1==i2 && a[i1][i2]==0){
numofo++;
if (numofo==3){
System.out.println("O2 WIN THE GAME");
break;
}
}
}
}
int sumAcross =0;
for (int i1=0;i1<3;i1++){
numofo =0;
numofx =0;
for(int i2 =0;i2<3;i2++){
// sumAcross += i2;
if ( a[i1][i2]==1){
numofx++;
if (numofx==3){
System.out.println("X3 WIN THE GAME");
break;
}
}
if ( a[i1][i2]==0){
numofo++;
if (numofo==3){
System.out.println("O3 WIN THE GAME");
break;
}
}
}
}
for (int i1=0;i1<3;i1++){
numofo =0;
numofx =0;
for(int i2 =0;i2<3;i2++){
// sumAcross += i2;
if ( a[i2][i1]==1){
numofx++;
if (numofx==3){
System.out.println("X4 WIN THE GAME");
break;
}
}
if ( a[i2][i1]==0){
numofo++;
if (numofo==3){
System.out.println("O4 WIN THE GAME");
break;
}
}
}
}
}
}堆排序
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68import java.util.Arrays;
import java.util.Scanner;
public class heapify{
public int[] getHeapsort(int[] arr){
return heapsort(arr,0,arr.length);
}
public int[] heapsort(int [] arr ,int index, int heapsize) {
if (arr == null && arr.length < 2) {
return arr;
}
heapinsert(arr, 0);
while (heapsize != 0){
swap(arr, 0 , --heapsize);
heapify(arr,0,heapsize);
}
return arr;
}
public void heapinsert(int[] arr ,int index ){
for(int i = index ; i<arr.length;i++){
while (arr[i] > arr[(i-1)/2]){
swap(arr,i,(i-1)/2);
i=(i-1)/2;
}
}
}
public int[] heapify(int[] arr,int index, int heapsize){
int left = index*2+1;
while (left < heapsize){
int largest = left+1 < heapsize && arr[left] < arr[left+1]? left+1 : left;//比较两个儿子的大小
largest = arr[largest] > arr[index] ? largest : index ;//比较大儿子和父的大小
if (largest == index){
break;
}
swap (arr , largest , index);
index = largest;
left = index*2+1;
}
return arr;
}
public int[] randomArray(int maxValue , int maxSize){
int[] arr = new int[(int)(Math.random()*maxSize)] ;
for (int i =0 ; i<arr.length;i++){
arr[i] =((int)(Math.random()*(maxValue+1))-(int)(Math.random()*maxValue));
}
return arr;
}
public int swap(int[] arr ,int largest, int index){
if (largest + index ==0){
return arr[index];
}
arr[largest] = arr[largest] ^ arr[index];
arr[index] = arr[largest] ^ arr[index];
arr[largest] = arr[largest] ^ arr[index];
return arr[index];
}
public static void main (String[] args){
heapify test = new heapify();
int[] arr = test.randomArray(100,100);
// int[] arr = {4,3,7,8,5,10,2,-1,1,1,1,2,43,3,0};
// int[] arr = {1,4};
test.getHeapsort(arr);
for(int i:arr){
System.out.println(i);
}
}
}- 距离为k的数组根据java自带的heap默认最小根[排序]
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
27import java.util.PriorityQueue;
public class sortArrayLesstanceK{
public void sortArray(int[] arr , int k ){
PriorityQueue<Integer> heap = new PriorityQueue<>();//创建的最小堆注入值时会自动排序
int index = 0;//变量放在外面方便其他函数访问
for( ; index<Math.min(arr.length,k);index++){
heap.add(arr[index]);
}
int i = 0;
for (; index<arr.length;i++ ,index++){
arr[i] = heap.poll();//最小距离堆排序遵循的规则就是进一个出一个
heap.add(arr[index]);
}
while (!heap.isEmpty()){
arr[i] = heap.poll();//这个函数是为了把上面heap中剩k个数弹出因为这个heap的最右边碰到arr的最右边就停下来了我们需要把剩下的heap中的数全部吐出来不然arr数组中就会缺少这k个值
}
}
public static void main (String[] args){
int[] arr = {4,3,2,5};
sortArrayLesstanceK test = new sortArrayLesstanceK();
test.sortArray(arr,2);
for (int i : arr){
System.out.println(i);
}
}
}- 基数排序
public class radixSort{ public int[] getRadixSort(int[] arr){ return radixSort(arr, 0, arr.length,maxbits(arr)); } public int maxbits(int[] arr){ int max = Integer.MIN_VALUE; for (int i = 0;i<arr.length;i++){ max = Math.max(max,arr[i]); } int bit = 0; while (max != 0 ){ max = max /10; bit ++; } return bit; } public int[] radixSort(int[] arr, int l ,int r,int bits){ final int bit = 10; for (int b = bits ;b>0 ; b--){ int[] count = new int[bit]; int[] bucket = new int[r-l+1]; for (int i1 = l ;i1<r;i1++){ int j = getDigital(arr[i1], b); count[j] ++; } for (int i2 = l+1 ;i2<bit;i2++){ count[i2] = count[i2] + count[i2-1]; } for (int i3 = r-1; i3 >=l ;i3--){ bucket[count[getDigital(arr[i3],b)]-1] = arr[i3]; count[getDigital(arr[i3],b)]--; } for (int i4 = l; i4<r;i4++){ arr[i4] = bucket[i4]; } } return arr; } public int getDigital(int in ,int b){ int bit = 0; int inFix = in; while (inFix != 0 ){ inFix = inFix /10; bit ++; } if(bit == 0){ return 0; } return in / ((int)Math.pow(10,bit -b))%10; } public static void main(String[] args){ radixSort test = new radixSort(); int[] arr = {10000,11122,12312,34234,52350}; test.getRadixSort(arr); for (int i : arr ){ System.out.println(i); } // System.out.println(test.maxbits(arr)); // System.out.println(test.getDigital(52352, 4)); } }
- 基数排序
- 距离为k的数组根据java自带的heap默认最小根[排序]