复杂度与排序
1.数据结构和算法概述：
1.什么是数据结构：
- 数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科
- 数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据
2.数据结构的分类：
-
逻辑结构：
-
a. 集合结构：集合结构数据元素除了属于同一个集合外，他们之间没有任何其他的关系
-
b. 线性结构：线性结构中的数据元素之间存在一对一的关系
-
c. 树形结构：树形结构中的数据元素之间存在一对多的层次关系
-
d. 图形结构：图形结构的数据元素是多对多的关系
-
-
物理结构：（逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也可以叫做存储结构）
-
顺序存储结构：
-
链式存储结构：
-
3.什么是算法：
- 算法是指解题方***而完整的描述，是一个系列解决问题的清晰指定，算法代表着用系统的方法解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出
- 根据一定的条件，对一些数据进行计算，得到需要的结果
2.算法分析：
1.算法的时间复杂度分析：
-
在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素：
- 算法采用的策略和方案；
- 编译产生的代码质量；
- 问题的输入规模(所谓的问题输入规模就是输入量的多少)；
- 机器执行指令的速度；
-
由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。
如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。
-
执行次数=执行时间
-
大O阶表示法：
- 用常数1取代运行时间中所有加法常数
- 在修改后的运行次数中，只保留高阶项
- 如果最高阶存在，且常数因子不为1，则去除与这个项相乘的常数
-
例：1=O(1) n+3=O(n) n^2+3=O(n^2)
-
复杂程度从低到高排序：
- O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)<O(n^3)
2.算法的空间复杂度分析：
-
基本数据类型内存占用情况：
-
计算机访问内存的方式都是一次一个字节：
-
一个引用（机器地址）需要8个字节表示
-
创建一个对象，每个对象的自身开销是16个字节
-
一般内存的使用，如果不够8个字节，都会被自动填充为8个字节
-
一个原始数据类型的数组一般需要24字节的头信息
-
算法的空间复杂度计算公式记作：S(n)=O(f(n)),其中n为输入规模，f(n)为语句关于n所占存储空间的函数。
public static int[] reverse1(int[] arr){
int n=arr.length; //申请4个字节
int temp; //申请4个字节
for(int start=0,end=n-1;start<=end;start++,end--){
temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
return arr;
}
public static int[] reverse2(int[] arr){
int n=arr.length; //申请4个字节
int[] temp=new int[n]; //申请n*4个字节+数组自身头信息开销24个字节
for (int i = n-1; i >=0; i--) {
temp[n-1-i]=arr[i];
}
return temp;
}
- 根据大O推导法则，算法一：空间复杂度为O(1),算法二：空间复杂度为O(n),所以从空间占用的角度讲，算法一要优于算法二。
3.排序：
1.Comparable接口：
//学生类
@Data
public class Student implements Comparable<Student>{
private String username;
private int age;
//定义比较规则
@Override
public int compareTo(Student o) {
return this.getAge()-o.getAge();
}
}
//测试类
public class Test {
public static void main(String[] args) {
Comparable max = getMax(stu1, stu2);
System.out.println(max);
}
//测试方法，获取两个元素中的较大值
public static Comparable getMax(Comparable c1,Comparable c2){
int cmp = c1.compareTo(c2);
if (cmp>=0){
return c1;
}else{
return c2;
}
}
}
2.冒泡排序：
-
相邻的元素做比较交换
-
第一次就将最大的元素放到最后（正序）
for(int i=1;i< arr.length;i++){ for(int j=0;j< arr.length-i;j++){ if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } }
3.选择排序：
-
从第一个元素开始和数组中最小的元素交换
-
先选出最小的元素下标
for(int i=0;i< arr.length-1;i++){ int min=i; for(int j=i;j< arr.length;j++){ if(arr[min]>arr[j]){ min=j; } } int temp=arr[i]; arr[i]=arr[min]; arr[min]=temp; }
4.插入排序：
-
将无序中的元素插入有序中，第二层循环逆序实现最小到最前
for(int i=1;i< arr.length;i++){ for(int j=i;j>0;j--){ if(arr[j]<arr[j-1]){ int temp=arr[j]; arr[j]=arr[j-1]; arr[j-1]=temp; } } }
5.希尔排序（分组的插入排序）：
-
选定一个增长量h，按照增长量h作为数据分组依据，对数据进行分组
-
对分好组的每一组数据完成插入排序
-
减少增长量，最小减为1，重复第二步操作
//希尔排序=分组+插入排序 private static void sort(int[] nums){ for (int index = nums.length-1; index >0; index=index/2) { for (int i = index; i < nums.length; i=i+index) { for (int j = i; j >0; j=j-index) { if(nums[j-1]>nums[j]){ int temp=nums[j]; nums[j]=nums[j-1]; nums[j-1]=temp; } } } } }
6.归并排序：
-
递归：
- 先执行后递归，正序输出
- 先递归后执行，逆序输出
-
归并排序：
-
分解：利用先递归后执行，将数组分解成无数小数组（当开始下标等于结束下标时停止）
-
归并：利用先递归后执行，往回走时每一层中两小数组作比较，将最小的元素放入额外数组，最后将额外数组元素赋予原数组
public class e归并排序 { private static void sort(int[] nums, int i, int j){ if(i<j){ int mid=(i+j)/2; sort(nums,i,mid); sort(nums,mid+1,j); Merge(nums, i, mid, j); } } private static void Merge(int[] nums, int i,int mid, int j){ int[] temp=new int[j-i+1]; //临时数组 int k=0; //临时数组的指针 int left=i;int right=mid+1; //指定两个数组开始的坐标 while(left<=mid&&right<=j){ if(nums[left]<nums[right]){ temp[k++]=nums[left++]; //将两个数组中其中小的元素赋给临时数组 }else{ temp[k++]=nums[right++]; } } //上面其中一个数组还有剩余元素的情况 while(left<=mid){ temp[k++]=nums[left++]; } while(right<=j){ temp[k++]=nums[right++]; } //将临时数组中的元素符合原数组 for (int m = 0; m < temp.length; m++) { nums[i++]=temp[m]; } } public static void main(String[] args) { int[] nums={4,6,1,6,8,2,3}; sort(nums,0,nums.length-1); System.out.println(Arrays.toString(nums)); } }
-
7.快速排序：
-
此处的 主元是左指针的元素
-
（对冒泡排序的一种改进）在往下递归时就排序，在往回走的时候把排序好的小数组进行合并，将左指针大于主元的元素和右指针小于主元的元素交换、实现小于主元的元素在主元左边，大于主元的元素在主元左边，并且将左指针的元素和主元进行交换达成交换主元进行递归
-
public class h快速排序双向扫描 { public static void QuickSort2(int[] arr,int start,int end){ if(start>=end){ return; } int index=getIndex2(arr,start,end); //主元 QuickSort2(arr,start,index); QuickSort2(arr,index+1,end); } public static int getIndex2(int[] arr,int left,int right){ int mid=arr[left]; //基准值 int i=left+1;int j=right; while(i<=j){ while(i<=j&&arr[j]>=mid){ // i<=j是必须 j--; } while(i<=j&&arr[i]<=mid){ i++; } if(i<j){ //前面运算会出现i>j的情况 int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } //更新主元,交换后数组中arr[j]左边的小，右边的大 int temp=arr[left]; arr[left]=arr[j]; arr[j]=temp; return j; } }
8.排序的稳定性：
- 稳定性的定义：
- 数组中A元素和B元素相等，并且A元素在B元素前面；如果使用某排序算法多次排序后，能保证A元素依赖在B元素前面，可以说这个算法是稳定的
4.力扣题：
1.三数之和15：
-
排序+对撞指针，思路：先排序，后遍历，当遍历到元素大于0时打破循环，当此次循环元素和上次循环元素相同时跳过此次循环，再建立对撞指针.....
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> list=new ArrayList<>(); for(int k=0;k<=nums.length-2;k++){ if(nums[k]>0){ //如果存在k值大于0等结果必大于0 break; } if(k>0&&nums[k]==nums[k-1]){ //重复元素 continue; } int i=k+1;int j=nums.length-1; while(i<j){ int count=nums[i]+nums[j]+nums[k]; if(count>0){ while(i<j&&nums[j]==nums[--j]); //先加1后运算 }else if(count<0){ while(i<j&&nums[i]==nums[++i]); }else{ List<Integer> temp=new ArrayList<>(); temp.add(nums[i]);temp.add(nums[j]);temp.add(nums[k]); list.add(temp); while(i<j&&nums[j]==nums[--j]); while(i<j&&nums[i]==nums[++i]); } } } return list; } }
2.最接近的三数之和16：
-
排序+对撞指针，先排序，再遍历建立对撞指针，如果等于就返回，记录和目标值最相近的元素；三数之和小于目标值就左指针++，三数之和大于目标值就右指针--（需要重复元素）
class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int res=nums[0]+nums[1]+nums[2]; for(int k=0;k<nums.length-2;k++){ int i=k+1;int j=nums.length-1; while(i<j){ int count=nums[i]+nums[j]+nums[k]; if(count==target){ return count; } if(Math.abs(target-count)<Math.abs(target-res)){ //如果绝对值小就记录它 res=count; } if(count<target){ i++; }else{ j--; } } } return res; } }
3.四数之和18：
-
排序+对撞指针，思路和三数之和一致，除此之外需要多循环一次，并且目标值可能小于数组中最小的元素。
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> list=new ArrayList<>(); if(nums.length<4){ return list; } Arrays.sort(nums); int res=nums[0]+nums[1]+nums[2]+nums[3]; for(int k=0;k<nums.length-3;k++){ if(k>0&&nums[k-1]==nums[k]){ continue; } for(int l=k+1;l<nums.length-2;l++){ if(l>k+1&&nums[l-1]==nums[l]){ continue; } int i=l+1;int j=nums.length-1; while(i<j){ int count=nums[k]+nums[l]+nums[i]+nums[j]; if(count==target){ list.add(Arrays.asList(nums[i],nums[j],nums[k],nums[l])); while (i<j && nums[i] == nums[i+1]){ i++; } i++; while (i<j && nums[j] == nums[j-1]){ j--; } j--; }else if(count<target){ i++; }else{ j--; } } } } return list; } }
4.字母异位词分组49：
-
排序，hash表，思路：对于字符串数组中的每一个字符串进行排序，这样就能使字母相同而位置不同的字符串有相同的地方；用Map<String,List>的hash表将排序后的字符串存为key，没有排序的存入list中；对于字符串的排序（可将划为字符数组，直接使用Arrays.sort(chars);排序）；本题使用map.getOrDefault(sb,new ArrayList())创建数组
//char[] chars=str.toCharArray(); //map.getOrDefault(sb,new ArrayList<String>()); class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String,List<String>> map=new HashMap<>(); for(String str:strs){ char[] chars=str.toCharArray(); Arrays.sort(chars); String sb=new String(chars); List<String> temp=map.getOrDefault(sb,new ArrayList<String>()); temp.add(str); map.put(sb,temp); } return new ArrayList<>(map.values()); } }
5.合并区间56：
-
自定义排序，思路：先对二维数组进行排序（需要重构Arrays.sort()） //遍历二维数组比较前数组[1]和后数组[0];如果可以合并但前数组[1]大于后数组[1]，则取前数组 //使用toArray()将集合转化为数组
//Arrays.sort(intervals,(a,b)->a[0]-b[0]); class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals,(a,b)->a[0]-b[0]); List<int[]> list=new ArrayList<>(); for(int[] nums:intervals){ if(list.size()==0||list.get(list.size()-1)[1]<nums[0]){ //比较前数组[1]和后数组[0] list.add(nums); }else{ list.get(list.size()-1)[1]=Math.max(nums[1],list.get(list.size()-1)[1]); } } return list.toArray(new int[list.size()][2]); } }
6.颜色分类75：
-
希尔排序：
class Solution { //希尔排序（分组+插入） public void sortColors(int[] nums) { for(int index=nums.length-1;index>0;index=index/2){ for(int i=index;i<nums.length;i++){ for(int j=i;j>0;j--){ if(nums[j]<nums[j-1]){ int temp=nums[j]; nums[j]=nums[j-1]; nums[j-1]=temp; } } } } } } -
归并排序：
class Solution { //归并排序（先递归后排序，合并两个有序小数组） public void sortColors(int[] nums) { sort(nums,0,nums.length-1); } private void sort(int[] nums,int i,int j){ if(i<j){ int mid=(i+j)/2; sort(nums,i,mid); sort(nums,mid+1,j); merge(nums,i,mid,j); } } //形同合并两个有序数组 private void merge(int[] nums,int i,int mid,int j){ int[] temp=new int[j-i+1]; int k=0; int left=i;int right=mid+1; while(left<=mid&&right<=j){ if(nums[left]<nums[right]){ temp[k++]=nums[left++]; }else{ temp[k++]=nums[right++]; } } while(left<=mid){ temp[k++]=nums[left++]; } while(right<=j){ temp[k++]=nums[right++]; } for(int l=0;l<temp.length;l++){ nums[i++]=temp[l]; } } } -
快速排序：
class Solution { //快速排序（改进的冒泡排序，先求值后递归，往下递归时就排序） public void sortColors(int[] nums) { sort(nums,0,nums.length-1); } private void sort(int[] nums,int i,int j){ if(i<j){ int mid=getindex(nums,i,j); sort(nums,i,mid-1); sort(nums,mid+1,j); } } private int getindex(int[] nums,int i,int j){ int com=nums[i]; int left=i+1;int right=j; while(left<=right){ while(left<=right&&nums[left]<=com){ left++; } while(left<=right&&nums[right]>=com){ right--; } if(left<right){ int temp=nums[left]; nums[left]=nums[right]; nums[right]=temp; } } int temp=nums[right]; nums[right]=nums[i]; nums[i]=temp; return right; } }
6.合并两个有序数组88：
-
思路：加入1数组后直接排序
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { for(int i=0;i<n;i++){ nums1[m+i]=nums2[i]; } Arrays.sort(nums1); } } -
思路：
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] temp=new int[nums1.length]; int k=0; int i=0;int j=0; while(i<m&&j<n){ if(nums1[i]<nums2[j]){ temp[k++]=nums1[i++]; }else{ temp[k++]=nums2[j++]; } } while(i<m){ temp[k++]=nums1[i++]; } while(j<n){ temp[k++]=nums2[j++]; } for(int l=0;l<temp.length;l++){ nums1[l]=temp[l]; } } }
7.对链表进行插入排序147：
-
思路：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode insertionSortList(ListNode head) { ListNode dump=new ListNode(0); //返回结点 dump.next=head; ListNode last=head; //上一结点 ListNode cur=head.next; //活动结点 while(cur!=null){ if(last.val<=cur.val){ //上一结点小于等于活动结点移动 last=last.next; }else{ ListNode pre=dump; //祖父结点 while(pre.next.val<=cur.val){ //选择适合的插入位置，祖父结点下一结点就是 pre=pre.next; } last.next=cur.next; //上一结点指向先指向活动结点下一个 cur.next=pre.next; pre.next=cur; } cur=last.next; } return dump.next; } }
投递海康威视等公司10个岗位 >
