|
1 | 1 | packageg3501_3600.s3510_minimum_pair_removal_to_sort_array_ii; |
2 | 2 |
|
3 | 3 | // #Hard #Array #Hash_Table #Heap_Priority_Queue #Simulation #Linked_List #Ordered_Set |
4 | | -// #Doubly_Linked_List #2025_04_09_Time_289_ms_(99.58%)_Space_82.88_MB_(17.23%) |
| 4 | +// #Doubly_Linked_List #2025_04_29_Time_278_ms_(98.94%)_Space_70.90_MB_(68.88%) |
5 | 5 |
|
6 | | -publicclassSolution { |
7 | | -privatestaticclassSegment { |
8 | | -privatefinalintstart; |
9 | | -privatefinalintend; |
10 | | -privateSegmentleft; |
11 | | -privateSegmentright; |
12 | | -privateintlIdx; |
13 | | -privatelonglNum; |
14 | | -privateintrIdx; |
15 | | -privatelongrNum; |
16 | | -privatebooleanok; |
17 | | -privatelongminSum; |
18 | | -privateintli; |
19 | | -privateintri; |
| 6 | +importjava.util.Arrays; |
20 | 7 |
|
21 | | -publicstaticSegmentinit(int[]arr) { |
22 | | -returnnewSegment(arr,0,arr.length -1); |
| 8 | +publicclassSolution { |
| 9 | +publicintminimumPairRemoval(int[]nums) { |
| 10 | +if (nums.length ==1) { |
| 11 | +return0; |
23 | 12 | } |
24 | | - |
25 | | -publicSegment(int[]arr,ints,inte) { |
26 | | -start =s; |
27 | | -end =e; |
28 | | -if (s >=e) { |
29 | | -lIdx =rIdx =s; |
30 | | -lNum =rNum =arr[s]; |
31 | | -minSum =Long.MAX_VALUE; |
32 | | -ok =true; |
33 | | -return; |
| 13 | +intsize = (int)Math.pow(2,Math.ceil(Math.log(nums.length -1.0) /Math.log(2))); |
| 14 | +long[]segment =newlong[size *2 -1]; |
| 15 | +Arrays.fill(segment,Long.MAX_VALUE); |
| 16 | +int[]lefts =newint[size *2 -1]; |
| 17 | +int[]rights =newint[size *2 -1]; |
| 18 | +long[]sums =newlong[nums.length]; |
| 19 | +Arrays.fill(sums,Long.MAX_VALUE /2); |
| 20 | +int[][]arrIdxToSegIdx =newint[nums.length][]; |
| 21 | +sums[0] =nums[0]; |
| 22 | +intcount =0; |
| 23 | +arrIdxToSegIdx[0] =newint[] {-1,size -1}; |
| 24 | +for (inti =1;i <nums.length;i++) { |
| 25 | +if (nums[i] <nums[i -1]) { |
| 26 | +count++; |
34 | 27 | } |
35 | | -intmid =s + ((e -s) >>1); |
36 | | -left =newSegment(arr,s,mid); |
37 | | -right =newSegment(arr,mid +1,e); |
38 | | -merge(); |
| 28 | +lefts[size +i -2] =i -1; |
| 29 | +rights[size +i -2] =i; |
| 30 | +segment[size +i -2] =nums[i -1] + (long)nums[i]; |
| 31 | +arrIdxToSegIdx[i] =newint[] {size +i -2,size +i -1}; |
| 32 | +sums[i] =nums[i]; |
39 | 33 | } |
40 | | - |
41 | | -privatevoidmerge() { |
42 | | -lIdx =left.lIdx; |
43 | | -lNum =left.lNum; |
44 | | -rIdx =right.rIdx; |
45 | | -rNum =right.rNum; |
46 | | -ok =left.ok &&right.ok &&left.rNum <=right.lNum; |
47 | | -minSum =left.minSum; |
48 | | -li =left.li; |
49 | | -ri =left.ri; |
50 | | -if (left.rNum +right.lNum <minSum) { |
51 | | -minSum =left.rNum +right.lNum; |
52 | | -li =left.rIdx; |
53 | | -ri =right.lIdx; |
54 | | - } |
55 | | -if (right.minSum <minSum) { |
56 | | -minSum =right.minSum; |
57 | | -li =right.li; |
58 | | -ri =right.ri; |
59 | | - } |
| 34 | +arrIdxToSegIdx[nums.length -1][1] = -1; |
| 35 | +for (inti =size -2;i >=0;i--) { |
| 36 | +intl =2 *i +1; |
| 37 | +intr =2 *i +2; |
| 38 | +segment[i] =Math.min(segment[l],segment[r]); |
60 | 39 | } |
| 40 | +returngetRes(count,segment,lefts,rights,sums,arrIdxToSegIdx); |
| 41 | + } |
61 | 42 |
|
62 | | -publicvoidupdate(inti,longn) { |
63 | | -if (start <=i &&end >=i) { |
64 | | -if (start >=end) { |
65 | | -lNum =rNum =n; |
| 43 | +privateintgetRes( |
| 44 | +intcount, |
| 45 | +long[]segment, |
| 46 | +int[]lefts, |
| 47 | +int[]rights, |
| 48 | +long[]sums, |
| 49 | +int[][]arrIdxToSegIdx) { |
| 50 | +intres =0; |
| 51 | +while (count >0) { |
| 52 | +intsegIdx =0; |
| 53 | +while (2 *segIdx +1 <segment.length) { |
| 54 | +intl =2 *segIdx +1; |
| 55 | +intr =2 *segIdx +2; |
| 56 | +if (segment[l] <=segment[r]) { |
| 57 | +segIdx =l; |
66 | 58 | }else { |
67 | | -left.update(i,n); |
68 | | -right.update(i,n); |
69 | | -merge(); |
| 59 | +segIdx =r; |
70 | 60 | } |
71 | 61 | } |
72 | | - } |
73 | | - |
74 | | -publicSegmentremove(inti) { |
75 | | -if (start >i ||end <i) { |
76 | | -returnthis; |
77 | | - }elseif (start >=end) { |
78 | | -returnnull; |
| 62 | +intarrIdxL =lefts[segIdx]; |
| 63 | +intarrIdxR =rights[segIdx]; |
| 64 | +longnumL =sums[arrIdxL]; |
| 65 | +longnumR =sums[arrIdxR]; |
| 66 | +if (numL >numR) { |
| 67 | +count--; |
79 | 68 | } |
80 | | -left =left.remove(i); |
81 | | -right =right.remove(i); |
82 | | -if (null ==left) { |
83 | | -returnright; |
84 | | - }elseif (null ==right) { |
85 | | -returnleft; |
| 69 | +longnewSum =sums[arrIdxL] =sums[arrIdxL] +sums[arrIdxR]; |
| 70 | +int[]leftPointer =arrIdxToSegIdx[arrIdxL]; |
| 71 | +int[]rightPointer =arrIdxToSegIdx[arrIdxR]; |
| 72 | +intprvSegIdx =leftPointer[0]; |
| 73 | +intnextSegIdx =rightPointer[1]; |
| 74 | +leftPointer[1] =nextSegIdx; |
| 75 | +if (prvSegIdx != -1) { |
| 76 | +intl =lefts[prvSegIdx]; |
| 77 | +if (sums[l] >numL &&sums[l] <=newSum) { |
| 78 | +count--; |
| 79 | + }elseif (sums[l] <=numL &&sums[l] >newSum) { |
| 80 | +count++; |
| 81 | + } |
| 82 | +modify(segment,prvSegIdx,sums[l] +newSum); |
| 83 | + } |
| 84 | +if (nextSegIdx != -1) { |
| 85 | +intr =rights[nextSegIdx]; |
| 86 | +if (numR >sums[r] &&newSum <=sums[r]) { |
| 87 | +count--; |
| 88 | + }elseif (numR <=sums[r] &&newSum >sums[r]) { |
| 89 | +count++; |
| 90 | + } |
| 91 | +modify(segment,nextSegIdx,newSum +sums[r]); |
| 92 | +lefts[nextSegIdx] =arrIdxL; |
86 | 93 | } |
87 | | -merge(); |
88 | | -returnthis; |
| 94 | +modify(segment,segIdx,Long.MAX_VALUE); |
| 95 | +res++; |
89 | 96 | } |
| 97 | +returnres; |
90 | 98 | } |
91 | 99 |
|
92 | | -publicintminimumPairRemoval(int[]nums) { |
93 | | -Segmentroot =Segment.init(nums); |
94 | | -intres =0; |
95 | | -while (!root.ok) { |
96 | | -intl =root.li; |
97 | | -intr =root.ri; |
98 | | -root.update(l,root.minSum); |
99 | | -root =root.remove(r); |
100 | | -res++; |
| 100 | +privatevoidmodify(long[]segment,intidx,longnum) { |
| 101 | +if (segment[idx] ==num) { |
| 102 | +return; |
| 103 | + } |
| 104 | +segment[idx] =num; |
| 105 | +while (idx !=0) { |
| 106 | +idx = (idx -1) /2; |
| 107 | +intl =2 *idx +1; |
| 108 | +intr =2 *idx +2; |
| 109 | +segment[idx] =Math.min(segment[l],segment[r]); |
101 | 110 | } |
102 | | -returnres; |
103 | 111 | } |
104 | 112 | } |