P2认识时间复杂度和简单排序算法

912. 排序数组

只要是排序相关的代码(冒泡,选择,插入)的测试都是在这个上面完成的

public class P2认识复杂度和简单排序算法{public static void main(String[] args){int[] arr={1,2,1,3,2,5};只出现一次的数字III a=new 只出现一次的数字III();System.out.println(a.s(arr));}}/*选择排序的基本思想:一遍又一遍的遍历数组,将最大的移到当前列表的末尾*1.从0位置到len(list)-1位置进行遍历,找出最小的数,与0交换位置*2.从1位置到len(list)-1位置进行遍历,找出最小的数,与1交换位置*不断重复以上操作*/// 13 / 13 个通过测试用例 应该写的没问题class selectionSort{public static int[] sort(int[] nums){for(int i=0;i<nums.length-1;i++){//最后一位元素nums.length-1其实不需要遍历,到他的时候列表以及变得有序了//用来记录最小值元素的下标int sub=i;for(int j=i+1;j<nums.length;j++){//进行比较if(nums[sub]>nums[j]){sub=j;}}//进行交换int temp=nums[i];nums[i]=nums[sub];nums[sub]=temp;}return nums;}}

====================================================================================================================================================================================================================================

/*冒泡排序基本思想:通过下标i的不停往右移动,使得i位置元素与i+1位置元素进行比较--如果i+1位置元素更小,则换位置--如果i位置元素更小,则不动通过这种方式可以将最大值移动到列表最后舍弃(无法达到)列表末尾,或者说切分数组将最大值"抛弃"(变换成更小的自己)*/// 10 / 13 个通过测试用例class bubbleSort{public static int[] sort(int[] nums){for(int i=0;i<nums.length;i++){//不取最后一位元素,防止溢出for(int j=0;j<nums.length-i-1;j++){if(nums[j]>nums[j+1]){//进行交换int temp=nums[j];nums[j]=nums[j+1];nums[j+1]=temp;/*交换还可以这样写:^:该符号代表异或,在离散数学中俩相同元素^,结果为00^n(n为任意)=n,所以有以下代码a=a^b运行结束后a=a^bb=a^b 这里是a^b^b所以b为aa=a^b 这里是a^b^a所以a为b*/}}}return nums;}}

====================================================================================================================================================================================================================================

260. 只出现一次的数字 III

136. 只出现一次的数字

/*关于异或的面试题:1.在一个数组中,只有一种数出现了奇数次,其他都出现了偶数次,怎么找到这个出现奇数次的数直接通过异或,所有相同数得到了0,这样最后就是 数和0(数^0)=数2.在一个数组中,有两种数出现了奇数次,其他都出现了偶数次,怎么找到这两个出现奇数次的数首先通过异或,得到eor=a^b,因为a与b不相同所以至少有一位对应数字为1<<这里可以假设a,b第八位为1,因为第八位只有0,1两种情况,所以可以以此分类a,b不属于同一类>>这里通过eor & (~eor+1)得到最右边对应1的数字*/class 只出现一次的数字{//136. 只出现一次的数字public static int s(int[] nums){//对数组进行遍历,相同元素在异或时会得到0//最后变为 数和0(数^0)=数int eor=0;for(int i=0;i<nums.length;i++){eor^=nums[i];}return eor;}}class 只出现一次的数字III{//260. 只出现一次的数字 IIIpublic static int[] s(int[] nums){int eor=0;for(int i=0;i<nums.length;i++){eor^=nums[i];}//因为eor=a^b//a,b不为同一数字//eor!=0//这里假设eor=1010111100//~eor=0101000011//~eor+1=0101000100//eor &(~eor+1)=0000000100int right=eor &(~eor+1);//获得最右边的1//再次遍历数组,找出所有8位为1的数字int eor_a=0;for(int i=0;i<nums.length;i++){if((right & nums[i])==0){//这里是做与运算,若结果等于0,说明当前元素"第八位"为0eor_a^=nums[i];}}int eor_b=eor_a^eor;int []a={eor_a,eor_b};return a;}}

====================================================================================================================================================================================================================================

/*插入排序的基本思想:假设有如下数组:[3,2,5,4,2,3,3]--首先使得0--1位置有序,从cur(当前为1)位置开始向前比较,碰到比cur位置大的元素交换位置,并将cur移动到改位置[2,3,5,4,2,3,3]--将0--2位置有序,从cur(当前为2)位置开始向前比较,碰到比cur位置大的元素交换位置,并将cur移动到改位置注意:在这个过程中遇见比cur位置小的元素即可停止插入(因为前面已经变得有序)--不断重复,直到排序完成插入排序的最坏时间复杂度为o(n**2),最优情况是[1,2,3,4,5]时间复杂度为o(n)但对于任何一个算法,都是以最坏的来估计所以插入排序为o(n**2)*///12 / 13 个通过测试用例class insertSort{public static int[] sort(int[] nums){for(int cur=1;cur<nums.length;cur++){//当前元素下标for(int j=cur-1;j>=0;j--){//比对次数if(nums[cur]<nums[j]){//这里需要对位置进行交换int temp=nums[j];nums[j]=nums[cur];nums[cur]=temp;//同时cur前移cur=j;}else{break; //当前位置元素大于等于当前位置-1元素,而前面已经有序,所以不需要往后走了}}}return nums;}}

====================================================================================================================================================================================================================================

704. 二分查找

/*二分查找的基本思想:首先二分查找只是针对于有序数组的假设有如下数组[10,14,21,22,33,40]我想要找到其中的数字10--首先将数组对半分mid=(0+5)//2=2,nums[2]=21,因为21大于10,所以取当前数组左边[10,14] (这里将21直接去掉)--再对半分mid=(0+1)//2 nums[0]=10,对应上了*/class binarySearch{public static int sort(int[] nums,int target){int left=0;int right=nums.length-1;while(left<=right){//可以相等,相当于列表只有一个元素int mid=(left+right)/2; //这里与python不一样整数与整数的运算,会自然得整数if(nums[mid]<target){//这里num在mid的右边left=mid+1; //这里的+1除了直接把当前mid的值排除减少计算量//还有当出现这种情况[-1,0,3,5,9,12] 目标值为2//若采用left=mid,right=mid的写法//可以看到mid=2,nums[2]=3//nums=[-1,0,3]//再次重复mid=1,nums[1]=0//nums=[0,3]//再次重复mid=0,nums[0]=0//nums=[0,3]//不断重复陷入<<死循环>.}else if(nums[mid]>target){right=mid-1;}else{return mid;}}return -1;}}

====================================================================================================================================================================================================================================

34. 在排序数组中查找元素的第一个和最后一个位置

/*在排序数组中查找元素的第一个和最后一个位置基本思想:假设有如下数组[1,2,2,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5] 而target=3--首先根据二分法得mid=(0+20)/2=10 nums[10]=4 又target<4,所以nums=[1,2,2,2,2,2,3,3,3,3]--根据二分法得mid=(0+9)//2=4 nums[4]=2 又target>2,所以nums=[2,3,3,3,3]--根据二分法得mid=(0+4)//2=2 nums[2]=3 又target=3,所以对该下标进行记录index=7(这里是针对最初始nums)如果是查找target元素,现在已经可以结束,但因为要返回所有target元素,所以需要继续nums=[2,3]--根据二分法得mid=(0+1)//2=0 nums[0]=2 又target>2 所以nums=[3]--根据二分法......target=3,所以index=6以上代码跑完后,我找到了查找元素得最左侧位置,这时可通过循环找到最后面位置*/class 二分查找变形{public static int[] s(int[] nums,int target){if(nums.length==1){if(target==nums[0]){return new int[]{0,0};}}int left=0;int right=nums.length-1;int index=-1;//这里是用来记录target在数组中最左侧位置while(left<=right){int mid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{index=mid;right=mid-1;}}//以上代码执行结束,会得到target在列表中得最左侧位置,若index值没有变过,说明数组中targetint right_copy=index;if(index!=-1){//在这里最开始我写的是index!=right,但right在上面代码的执行过程中发生了改变for(int i=index+1;i<nums.length;i++){if(nums[i]==target){right_copy+=1;}}return new int[]{index,right_copy};}return new int[]{-1,-1};}}

====================================================================================================================================================================================================================================

162. 寻找峰值

这个题目也是二分查找的变形,但对应的是无序的数组,思想上还有些许不太

清楚的地方多看

/*了解局部最大:假设有一数组:[2,1,3,1] 下标为0位置处的2就是局部最大假设有一数组:[1,3,4,5] 下标为n-1位置的5就是局部最大假设有一数组:[1,3,2,1] 下标为1位置的3就是局部最大--以上就是三种局部最大的情况局部最大的基本思路:--先将0位置元素与1位置元素比较,如果0位置元素更大,即可直接返回--若不满足,再将n-1位置与n-2位置元素进行比较,如果n-1位置元素更大,即可返回--若上面两种情况都不满足 则说明0-->1位置单调递增,n-2位置到n-1位置单调递减--再加上nums[i] != nums[i + 1](相邻元素不相等)*****一定存在拐点(至少一个)--加上有一数组nums=[1,2,1,3,5,6,4]--mid=(0+6)//2nums[3]=3 nums[3]>nums[2] 说明2到3位置单调递增这样就是0-->1单调递增 2-->3单调递增无法说明中间(0-->3)有拐点但:2-->3单调递增 n-2到n-1单调递减 ,所以2到n-1一定有拐点重复以上步骤*/class 寻找峰值{//局部最小题目没找到,所以来一个局部最大的public static int sort(int[] nums) {if (nums.length == 1) return 0;if (nums[0] > nums[1]) return 0;int right = nums.length - 1;if (nums[right] > nums[right - 1]) return right;int left = 0;while (left < right) {int mid = (left + right) / 2;if (nums[mid] > nums[mid + 1]) {right = mid; //只要经历过一次,那么当前mid对应的数就再也不会当mid//如果这里写mid-1//那么mid-1与mid是没有判断过的,当然不可以} else {//能进来说明此时nums[mid]<nums[mid+1]left = mid + 1;//这里mid与mid+1比较过,直到mid-->mid+1是增加//所以可以这样写,默认最左侧的数字是通过增加得到//这样到后面只剩下两个的时候//[5,4] nums[mid]=5 5>4 将right=0}}return left;}}

====================================================================================================================================================================================================================================

/*对数器(对比数据的机器):用来帮助你自己测试代码的方法--写两个一样的方法,给大量的随机数据(random),分别测试,比较结果*/

====================================================================================================================================================================================================================================

====================================================================================================================================================================================================================================

P3认识o(nlogn)的排序

找出数组中的最大值

import java.util.*;public class P3认识nlogn的排序{public static void main(String[] args) {数组最大值 a=new 数组最大值();a.ceshi();}}class 数组最大值{public static int s(int[] nums,int left,int right){if(left==right){return nums[left];}int mid=(left+right)/2;int nums_left=s(nums,left,mid);int nums_right=s(nums,mid+1,right);//mid对应的数只需要在一个子数组里面return Math.max(nums_left,nums_right); //python中可以直接写max 这里面需要写Math.max//一个是关键字一个是方法}public static boolean 测试(){int maxsize=10000;int maxshuju=1000;int[] nums = new int[(int) (maxsize * Math.random())];for (int i = 0; i < nums.length; i++) {nums[i] = (int) (maxshuju * Math.random());int[] nums_copy = nums.clone();Arrays.sort(nums_copy);return nums_copy[nums_copy.length - 1] == s(nums, 0, nums.length - 1);}return true;}public static void ceshi(){for(int i=0;i<10000;i++){System.out.println(测试());}}}

这里有一个细节:平时我们求中点基本上都是这样写int mid=(left+right)/2这样如果你数组开的特别大,left和right的和溢出了java中整数的范围就会导致计算结果出错(python中不需要去考虑这些)这样写会好一些int mid=left+(right-left)/2

====================================================================================================================================================================================================================================

等问题规模的递归才可以使用

int mid=(left+right)/2;int nums_left=s(nums,left,mid);int nums_right=s(nums,mid+1,right);//mid对应的数只需要在一个子数组里面

这里每次对半分,问题规模都为原来的1/2,调用两次

所以master公式为:T(N)=2*T(N/2)+0(1)<<其他操作为常数级>>

====================================================================================================================================================================================================================================

归并排序

912. 排序数组

/*归并排序的基本思想:假如有一数组:[3,1,4,5,9,7]不断二分可变为[3,1,4,5,9,7][3,1,4] [5,9,7][3,1] [4][3] [1]等当前只有一个元素时,直接return;然后将当前两个数组排序变为[1,3]在与[4]排序变为[1,3,4]右边同样归并排序思路再次整理:首先就是通过递归不断的二分,上面已经有了对于[3][1]首先根据left和right开辟空间help再将他俩排序help=[1,3]将nums进行更改nums=[1,3,4,5,9,7]对于 [1,3][4]首先是根据left和right开辟空间help在将他俩排序放入help中help=[1,3,4]将nums进行更改nums=[1,3,4,5,9,7]对于[5][9]首先根据left和right开辟空间help再将他俩排序help=[5,9]将nums进行更改nums=[1,3,4,5,9,7]对于[5,9][7]首先根据left和right开辟空间help再将他俩排序help=[5,7,9]将nums进行更改nums=[1,3,4,5,7,9]对于[1,3,4][5,7,9]首先根据left和right开辟空间help再将他俩排序help=[1,3,4,5,7,9]将nums进行更改nums=[1,3,4,5,7,9]可以看到我一直再重复某些话,所以就是将其分解成为更小的自己进行排序使用递归*/class 归并排序{public static int[] s(int[] nums){main(nums,0,nums.length-1);//因为nums是引用数据类型,上面传参时传入的是引用的复制体//所以都是对同一个在堆内存中存储的nums进行更改//所以可以直接return nums;}public static void main(int[] nums,int left,int right){//列表中只包含一个元素,直接返回if(left==right) return;int mid=(left+right)/2;//去除中间值main(nums,left,mid);main(nums,mid+1,right);//调用sort进行排序sort(nums,left,mid,right);}public static void sort(int[] nums,int left,int mid,int right){int[] help=new int[right-left+1];//开辟内存空间用来暂时存放排序数组int i=0;int l=left;int r=mid+1;while(l<=mid && r<=right){//mid是左子列表的最右侧 right是右子列表的最右侧if(nums[l]<nums[r]){help[i++]=nums[l++];}else{help[i++]=nums[r++];}}//出来的时候可能有一个未遍历结束while(l<=mid){help[i++]=nums[l++];}while(r<=right){help[i++]=nums[r++];}//开始对原数组nums进行更改for(int j=0;j<help.length;j++){nums[left+j]=help[j];}}}

====================================================================================================================================================================================================================================

这个是归并排序的变形,我好像写的有问题,但暂时先放着了

315. 计算右侧小于当前元素的个数

/*计算小和问题:题目描述:在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和.现在求一个数组的小和例如:[1,3,4,2,5]1左边比1小的数没有小和=03左边比3小的数为1 小和=14左边比4小的数为1,3小和=42............1 小和=15..........1,3,4,2 小和=10数组的小和即为16基本思想:如果采用暴力的方法当然是很好想的--当到达当前数时,拿当前数和左边的所有数比较一遍,记录和即可--时间复杂度达到了o(n**2)当然是有更好的办法:1右边比1大的数3,4,2,5 所以这几个数计算小和时都会加1 43右边比3大的数4,5 所以这几个数计算小和时都会加3 64.......5 ......... 4 42.............5 ....... 2 2数组的小和即为 4+6+4+2=16这时候如果直接当前数的右边进行遍历,与最开始的暴力解法没什么区别当依靠上面的思想有一种很好的方法,归并排序[1,3,4,2,5][1,3,4][2,5][1,3] [4] [2] [5][1] [3]在每次的排序过程中都会进行一次比较,如果这次比较中< 则计算数组和的变量可以+nums[cur]当前元素,这个过程中不会出现漏算或重算的情况注意:1.在两指针指向位置相等的情况下,右侧列表后移:[1,1,1,2,2,3,3] [1,1,1,2,2,6,6]如果移动左侧列表指针,会导致小和漏算2.排序过程不能省略就是通过排序,在计算小和是可以直接通过下标*/class 计算右侧小于当前元素的个数{public List<Integer> main(int[] nums){//这个排序是从大往小排,因为统计右侧小于当前元素的个数int[] index=new int[nums.length];for(int i=0;i<nums.length;i++){index[i]=i;}int[] tongji=new int[nums.length]; //开辟空间,里面默认存放的是0,正好不需要更改s(nums,0,nums.length-1,tongji,index);//这里是负责对nums进行排序,在这个过程中tongji同样在发生改变List<Integer> c=new ArrayList<>();for(int i=0;i<tongji.length;i++){c.add(tongji[i]);}return c;}public void s(int[] nums,int left,int right,int[] tongji,int[] index){if(left==right) return; //说明对应只有一个元素,数组已经不可再分,就停止分裂int mid=(left+right)/2;s(nums,left,mid,tongji,index);s(nums,mid+1,right,tongji,index);//将这个两个有序列表,进行有序合并sort(nums,left,mid,right,tongji,index);}public void sort(int[] nums,int left,int mid,int right,int[] tongji,int[] index){int[] help=new int[right-left+1]; //开辟帮助空间int i=0;int l=left; //左子数组最左侧int r=mid+1;//右子数组最左侧while(l<=mid && r<=right){if(nums[l]<=nums[r]){help[i]=nums[r]; //从大到小排列//换位置int temp=index[left+i];index[left+i]=index[r];index[r]=temp;i++;r++;}else{//一定是nums[l]大于nums[r]才进来//这时候属于当前元素的右侧小于,可以记录//换位置tongji[index[l]]+=1;int temp=index[left+i];index[left+i]=index[l];index[l]=temp;help[i++]=nums[l++];}}//出来时可能存在一数组没遍历完的情况while(l<=mid){//换位置int temp=index[left+i];index[left+i]=index[l];index[l]=temp;help[i++]=nums[l++];}while(r<=right){//换位置int temp=index[left+i];index[left+i]=index[r];index[r]=temp;help[i++]=nums[r++];}for(int j=0;j<help.length;j++){nums[left+j]=help[j];}}}

============================================================================================================================================================================================================================

同样是归并排序的变形,这个写出来了

剑指 Offer 51. 数组中的逆序对

/*逆序对问题:在一个数组中,左边的数如果比右边大,则这两个数构成一个逆序对,请打印所有逆序[3,2,5,0,1] 3,2 3,03,12,02,1 5,05,1这个题目和归并上面的区别不大*/class 数组中的逆序对{int sum;public 数组中的逆序对(){this.sum=0;}public int reversePairs(int[] nums){int right=nums.length-1;if(right<0)return 0;digui(nums,0,right);return sum;}public void digui(int[] nums,int left,int right){if(left==right) return;int mid=(left+right)/2; //这种计算易存在溢出情况,但写习惯了,/直接取整digui(nums,left,mid);digui(nums,mid+1,right);//这里好像不需要赋值,先这样写着把int[] help=new int[right-left+1];//开辟空间int l=left;int r=mid+1;int i=0;//用来记录help的下标到了第几个while(l<=mid && r<=right){//这里可以等于吗?if(nums[l]>nums[r]){//如果计算结果有问题,可以确定是这里的问题help[i]=nums[l];//左边大可以形成逆序对l+=1;i+=1;this.sum+=right-r+1;//注意咱们是从大到小排,如果当前的l比当前的r大,那么l一定比后面的大}else{help[i]=nums[r];r+=1;i+=1;}}//这里可能存在某一数组未被遍历完while(l<=mid){help[i]=nums[l];l+=1;i+=1;}while(r<=right){help[i]=nums[r];r+=1;i+=1;}//再把数组中排好序的放在nums里面for(int j=0;j<help.length;j++) {nums[j + left] = help[j];}}}

============================================================================================================================================================================================================================

荷兰国旗问题,这个在leetcode上没找到,自己测了一下,应该没问题

/*荷兰国旗问题:*//*问题一:给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边,大于num的数放在数组的右边要求额外空间复杂度o(1),时间复杂度o(n)问题一基本思想:#最后得到的结果是:小于等于区和大于区,通过小于等于区扩张,将大于区推到最右边#小于等于区最开始为空ls=[3,5,6,7,4,3,5,8],假设num=5,当前下标为i1.如果ls[i]<=num,i和小于等于区下一个元素换位置,i+12.如果ls[i]>num,i+1(这样小于区和i之间是大于区,i之后是待定区)*/public class P3认识nlogn排序2{public static void main(String[] args){荷兰问题二 a=new 荷兰问题二();int[] c={3,5,6,74,3};//注意这种方式就是为了获得小于等于区,和大于区,所以num不必在中间c=a.s(c,5);for(int i=0;i<c.length;i++)System.out.println(c[i]);}}class 荷兰问题一{//[3,5,3,74,6]public int[] s(int[] nums,int num){int xiaoyu=-1;for(int i=0;i<nums.length;i++){if(nums[i]<=num){//最小区向外扩张xiaoyu+=1;int t=nums[xiaoyu];nums[xiaoyu]=nums[i];nums[i]=t;}//如果是大于//那么只需要i+1向后移,再加上写的是for循环,所以什么都不需要干}return nums;}}/*问题二:给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间大于num的数放在数组的右边问题二思路:我最终要得到的结果是一个小于区,一个等于区,一个大于区现在的思路是最左侧为小于区,最右侧为大于区,大于区向"左扩"小于区向"右扩",大于区和小于区的中间部分就是等于区设当前位置为i1.nums[i]<num,nums[i]和小于区下一个元素交换,小于区"右扩",i+12.nums[i]=num,i+13.nums[i]>num,nums[i]与大于区前一个交换,大于区左扩,i不变(这里是因为小于区的交换是对于已经看过的数,但是大于区的数没有看过)*/class 荷兰问题二{//[3,3,5,74,6]public int[] s(int[] nums,int num){int xiaoyu = -1;int dayu = nums.length;int i = 0;while (i < dayu){if (nums[i] < num) {xiaoyu += 1;int t = nums[xiaoyu];nums[xiaoyu] = nums[i];nums[i] = t;i+=1;} else if (nums[i] == num) {i += 1;} else {dayu -= 1;int t = nums[dayu];nums[dayu] = nums[i];nums[i] = t;}}return nums;}}

============================================================================================================================================================================================================================

这个题与荷兰国旗问题二的思想一样,只是只有3个数而已

75. 颜色分类

class 颜色分类{public void sortColors(int[] nums) {int xiaoyu=-1;int dayu=nums.length;int i=0;while(i<dayu){//这里以大于作为参考,因为大于后面的都是比num大的数if(nums[i]<1){xiaoyu+=1;int t=nums[xiaoyu];nums[xiaoyu]=nums[i];nums[i]=t;i+=1;}else if(nums[i]==1){i+=1;}else{dayu-=1;int t=nums[dayu];nums[dayu]=nums[i];nums[i]=t;}}}}

============================================================================================================================================================================================================================

912. 排序数组

这个就是荷兰国旗问题一加上了递归

单指针的快速排序这是第一次写

快排的空间复杂度为o(logn)

class 快速排序一点零{public static int[] s(int[] nums){sort(nums,0,nums.length-1);return nums;}public static void sort(int[] ls,int left,int right){if(left>=right) return;//结束掉递归//这个是用来排序的玩意//这里可以拿中间的或者最左边,最右边的当中值,这里我选择最右边,因为看的视频是这样的哈哈哈//平时我用的是双指针,不过试试单指针也好int xiaoyu=left-1;int zhongzhi=ls[right];int i=left;while(i<right){if(ls[i]<=zhongzhi) {//小于等于区域需要扩张xiaoyu += 1;//i和小于之间的一定是大于int t = ls[xiaoyu];ls[xiaoyu] = ls[i];ls[i] = t;}//如果大于了什么都不需要干i+=1;}//现在i在right位置,一定是会换一下的xiaoyu += 1;//i和小于之间的一定是大于int t = ls[xiaoyu];ls[xiaoyu] = ls[i];ls[i] = t;sort(ls,left,xiaoyu-1);sort(ls,xiaoyu+1,right);return;}}

============================================================================================================================================================================================================================

912. 排序数组

堆最重要的不是排序,他只是恰好有这个性质而已

入堆和出堆就可以了

对于已经给定的数组,就是一个完全二叉树

你可以直接在这个数组上进行堆排序,从右往左(数组)不断循环,向下

判断.这样比再开辟空间,一个一个入堆好一些,时间复杂度好一些

堆在很多时候都是需要自己手写的,因为有些操作,别人再写的时候

为了使用方便,操作效率是低的.

class dui{int[] dui_shuzu;int size;public dui(int kongjian){this.dui_shuzu=new int[kongjian+1];//我喜欢把数组第一个位置空出来,相对看着方便this.size=0;}public void rudui(int item){this.size+=1;//因为有个元素进来了,所以size+1int i=this.size; //这是这个元素当前的位置this.dui_shuzu[i]=item;while(i/2>0){int zi=this.dui_shuzu[i];int fu=this.dui_shuzu[i/2];if(zi<fu){//子节点小于父节点,需要换位置int t=zi;this.dui_shuzu[i]=fu;this.dui_shuzu[i/2]=t;i/=2;//当前位置换到父位置}else{break;//只要有一次不满足直接结束掉}}}public int chudui(){//出堆的话有个技巧,如果你直接删除,会造成元素的移动,时间复杂度高//可以直接拿最后面的元素覆盖出堆元素//然后该元素不断下沉int res=11111;int i=1;//出堆if(size>0){res=this.dui_shuzu[1];//需要返回的结果this.dui_shuzu[1]=this.dui_shuzu[this.size];//用size覆盖掉this.size-=1;//开始下沉while(2*i<=size){//能进来说明有子节点int t=this.bijiao(i);if(this.dui_shuzu[i]>this.dui_shuzu[t]){//换位置int z=this.dui_shuzu[i];this.dui_shuzu[i]=this.dui_shuzu[t];this.dui_shuzu[t]=z;i=t;//当前位置替换到了t(较小的子节点)}else break;}}return res;}public int bijiao(int i){//这个是用来比较左右子节点大小的元素int zuo=2*i;int you=2*i+1;//只有三种情况,没有左右子节点,只有左子节点,既有左又有右//但是能到这里来只能是只有左子节点,既有左又有右if(you>this.size) return zuo;else{if(this.dui_shuzu[zuo]<this.dui_shuzu[you]){return zuo;}else{return you;}}}}

============================================================================================================================================================================================================================

387. 字符串中的第一个唯一字符

#这玩意和数组中的第一个数字一样的hash表就能做'''方法一:循环+hash表'''def fun1(s):dic={}#哈希表for i in range(len(s)):if s[i] in dic:#[i]已经在字典当中#可以进行删除操作#dic.pop(s[i]) 这里不能删除,如果该元素出现了奇数次那么会导致第三次出现的时候被误替了dic[s[i]]=-1#索引不可能出现-1else:#不在字典中dic[s[i]]=i#让他进去#检查一下字典for i in dic:if dic[i]!=-1:return dic[i]#一般元素都是看似尾部的添加return -1'''方法二:队列,队列本身具有先进先出的性质,在每次入对的时候进行一个判断,看元素的首位是否等同于入对元素,如果是进行出队操作.这样的话,遍历一遍字符串得到的队列的首位就是首个不重复元素'''def fun2(s):#开辟队列空间duilie=[-1]*len(s)duilie[0]=[s[0],0]#记录出现多次但未删除元素dic={}#当前首位shouwei=0for i in range(1,len(s)):if s[i]==s[shouwei][0]#print(fun2("aabb"))