@@ -266,6 +266,7 @@ https://github.com/h2pl/SwordToOffer
266266
267267
268268
269+
269270 该算法的时间复杂度是多少呢？考虑最坏情况下，每次 partition 将数组分为长度为 N-1 和 1 的两部分，然后在长的一边继续寻找第 K 大，此时时间复杂度为 O(N^2 )。不过如果在开始之前将数组进行随机打乱，那么可以尽量避免最坏情况的出现。而在最好情况下，每次将数组均分为长度相同的两半，运行时间 T(N) = N + T(N/2)，时间复杂度是 O(N)。
270271
271272所以也就是说，本题用这个方法解的话，复杂度只需要O（n),因为第一次交换需要N/2,j接下来的交换的次数越来越少，最后加起来就是O（N）了。
@@ -304,11 +305,11 @@ https://github.com/h2pl/SwordToOffer
304305
305306
306307
307- for(int i=0;i<input.length;i++){
308- if(treeSet.size()<k){
309- treeSet.add(input[ i] );
310- }
311-
308+ for(int i=0;i<input.length;i++){
309+ if(treeSet.size()<k){
310+ treeSet.add(input[ i] );
311+ }
312+
312313 else {
313314
314315 if(input[ i] <treeSet.last()){
@@ -565,7 +566,7 @@ LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2
565566
566567
567568
568- }
569+ }
569570
570571## 滑动窗口中的最大值
571572
@@ -667,30 +668,30 @@ LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2
667668
668669
669670
670- public class 替换空格 {
671- public static String replaceSpace(StringBuffer str) {
672- int newlen = 0;
673- for(int i = 0; i < str.length(); i++) {
674- if(str.charAt(i) == ' ') {
675- newlen = newlen + 3;
676- }
677- else {
678- newlen ++;
679- }
680- }
681- char [ ] newstr = new char[ newlen] ;
682- int j = 0;
683- for(int i = 0 ; i < str.length(); i++) {
684- if (str.charAt(i) == ' ') {
685- newstr[ j++] = '%';
686- newstr[ j++] = '2';
687- newstr[ j++] = '0';
688- }else {
689- newstr[ j++] = str.charAt(i);
690- }
691- }
692- return String.valueOf(newstr);
693- }
671+ public class 替换空格 {
672+ public static String replaceSpace(StringBuffer str) {
673+ int newlen = 0;
674+ for(int i = 0; i < str.length(); i++) {
675+ if(str.charAt(i) == ' ') {
676+ newlen = newlen + 3;
677+ }
678+ else {
679+ newlen ++;
680+ }
681+ }
682+ char [ ] newstr = new char[ newlen] ;
683+ int j = 0;
684+ for(int i = 0 ; i < str.length(); i++) {
685+ if (str.charAt(i) == ' ') {
686+ newstr[ j++] = '%';
687+ newstr[ j++] = '2';
688+ newstr[ j++] = '0';
689+ }else {
690+ newstr[ j++] = str.charAt(i);
691+ }
692+ }
693+ return String.valueOf(newstr);
694+ }
694695
695696
696697## 第一次只出现一次的字符
@@ -1207,30 +1208,30 @@ public static int LastRemaining_Solution(int n, int m) {
12071208
12081209
12091210
1210- void Mirror(TreeNode root) {
1211- if(root == null)return;
1212- Mirror(root.left);
1213- Mirror(root.right);
1214- if(root.left!=null || root.right!=null)
1215- {
1216- TreeNode temp=root.left;
1217- root.left=root.right;
1218- root.right=temp;
1219- }
1211+ void Mirror(TreeNode root) {
1212+ if(root == null)return;
1213+ Mirror(root.left);
1214+ Mirror(root.right);
1215+ if(root.left!=null || root.right!=null)
1216+ {
1217+ TreeNode temp=root.left;
1218+ root.left=root.right;
1219+ root.right=temp;
1220+ }
12201221
12211222
12221223
1223- }
1224- boolean isSameTree(TreeNode t1,TreeNode t2){
1225- if(t1==null && t2==null)return true;
1226- else if(t1!=null && t2!=null && t1.val==t2.val) {
1227- boolean left = isSameTree(t1.left, t2.left);
1228- boolean right = isSameTree(t1.right, t2.right);
1229- return left && right;
1230- }
1231- else return false;
1232- }
1233-
1224+ }
1225+ boolean isSameTree(TreeNode t1,TreeNode t2){
1226+ if(t1==null && t2==null)return true;
1227+ else if(t1!=null && t2!=null && t1.val==t2.val) {
1228+ boolean left = isSameTree(t1.left, t2.left);
1229+ boolean right = isSameTree(t1.right, t2.right);
1230+ return left && right;
1231+ }
1232+ else return false;
1233+ }
1234+
12341235 TreeNode copyTree (TreeNode root) {
12351236 if (root == null) return null;
12361237 TreeNode t = new TreeNode(root.val);
@@ -1530,6 +1531,7 @@ public static int LastRemaining_Solution(int n, int m) {
15301531
15311532
15321533
1534+
15331535 注意：但是当arr[left] = arr[right] = arr[min]时。三个数都相等无法确定最小值，此时只能遍历。
15341536
15351537# 递归
0 commit comments