递归实现
public static void merge(int[] arr,int L,int M,int R){
int[] help=new int[R-L+1];
int i=0;
int p1=L;
int p2=M+1;
while(p1<=M&&p2<=R){
help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=M){
help[i++]=arr[p1++];
}
while(p2<=R){
help[i++]=arr[p2++];
}
for( i=0;i<help.length;i++){
arr[L+i]=help[i];
}
}
public static void mergeSort1(int[] arr){
if(arr==null||arr.length<2){
return;
}
process(arr,0,arr.length-1);
}
public static void process(int[] arr,int L,int R){
if(L==R){
return;
}
int mid=L+((R-L)>>1);
process(arr,L,mid);
process(arr,mid+1,R);
merge(arr,L,mid,R);
}
非递归实现
public static void Mergersort2(int[] arr){
if(arr==null||arr.length<2){
return;
}
int N=arr.length;
int mergeSize=1;
while(mergeSize<N){
int L=0;
while(L<N){
int M=L+mergeSize-1;
if(M>=N){
break;
}
int R=Math.min(M+mergeSize,N-1);
merge(arr,L,M,R);
L=R+1;
}
if(mergeSize>N/2){
break;
}
mergeSize<<=1;
}
}
public static void merge(int[] arr,int L,int M,int R){
int[] help=new int[R-L+1];
int i=0;
int p1=L;
int p2=M+1;
while(p1<=M&&p2<=R){
help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=M){
help[i++]=arr[p1++];
}
while(p2<=R){
help[i++]=arr[p2++];
}
for( i=0;i<help.length;i++){
arr[L+i]=help[i];
}
}
public static void swap(int[] arr,int a,int b){
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void splitNum(int[] arr){
int lessEqualR=-1;
int index=0;
int N=arr.length;
while(index<N){
if(arr[index]<=arr[N-1]){
swap(arr,++lessEqualR,index++);
}
else{
index++;
}
}
}
public static void splitNum2(int[] arr){
int N=arr.length;
int lessR=-1;
int moreL=N-1;
int index=0;
while(index<moreL){
if(arr[index]<arr[N-1]){
swap(arr,index++,++lessR);
}
else if (arr[index]==arr[N-1]) {
index++;
}
else{
swap(arr,index,--moreL);
}
}
swap(arr,N-1,moreL);
}
public static int[] partition(int[] arr,int L,int R) {
int Less = L - 1;
int More = R;
int index = 0;
while (index < More) {
if (arr[index] > arr[R]) {
swap(arr, index, --More);
} else if (arr[index] == arr[R]) {
index++;
} else {
swap(arr, index++, ++Less);
}
}
swap(arr, More, R);
return new int[]{Less+1,More};
}
public static void process(int[] arr,int L,int R){
if(L>=R){
return;
}
int[] equal=partition(arr,L,R);
process(arr,L,equal[0]-1);
process(arr,equal[1]+1,R);
}
public static void quicksort(int[] arr){
if(arr==null||arr.length<2){
return;
}
process(arr,0,arr.length-1);
}
public static int f1(int[] arr){
int ans=0;
for(int i=0;i<arr.length;i++){
ans^=arr[i];
}
return ans;
}
public static int[] f2(int[] arr){
int eor=0;
for(int i=0;i<arr.length;i++){
eor^=arr[i];
}
int right=eor&(~eor+1);
int Onlyone=0;
for(int i=0;i<arr.length;i++){
if((arr[i]&right)==0){
Onlyone^=arr[i];
}
}
return new int[]{Onlyone,eor^Onlyone};
}
public static class MyStack1{
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack1(){
this.stackData=new Stack<Integer>();
this.stackMin=new Stack<Integer>();
}
public void push(int newNum){
if(this.stackMin.isEmpty()){
this.stackMin.push(newNum);
}
else if(newNum<this.getmin()){
this.stackMin.push(newNum);
}
else {
int newMin=this.stackMin.peek();
this.stackData.push(newMin);
}
this.stackData.push(newNum);
}
public int pop(){
if(this.stackData.isEmpty()){
throw new RuntimeException("Your stack is empty");
}
this.stackMin.pop();
return this.stackData.pop();
}
public int getmin(){
if(this.stackMin.isEmpty()){
throw new RuntimeException("Your stack is empty");
}
return this.stackMin.peek();
}
}
数组中只有一种树出现了K次，其他数都出现了M次，K<M返回那个数
public static int onlyKTimes(int[] arr,int k,int m){
int[] t=new int[32];
for(int num:arr){
for(int i=0;i<31;i++){
t[i]+=(num>>i)&1;
}
}
int ans=0;
for(int i=0;i<32;i++){
if(t[i]%m!=0){
ans|=(1<<i);
}
}
return ans;
}
public static int onlyKTimes(int[] arr,int k,int m){
int[] t=new int[32];
for(int num:arr){
for(int i=0;i<31;i++){
t[i]+=(num>>i)&1;
}
}
int ans=0;
for(int i=0;i<32;i++){
if(t[i]%m!=0){
ans|=(1<<i);
}
}
return ans;
}
public static int test(int[] arr,int k,int m){
HashMap<Integer,Integer> map=new HashMap<>();
for(int num:arr){
if(map.containsKey(num)){
map.put(num,map.get(num)+1);
}
else{
map.put(num,1);
}
}
for(int num:map.keySet()){
if(map.get(num)==k){
return num;
}
}
return -1;
}
public static int[] randomArray(int maxKinds,int range,int k,int m){
int ktimeNum=randomNumber(range);
int numKinds=(int)(Math.random()*maxKinds)+2;
int[] arr=new int[k+(numKinds-1)*m];
int index=0;
for(;index<k;index++){
arr[index]=ktimeNum;
}
numKinds--;
HashSet<Integer> set=new HashSet<>();
set.add(ktimeNum);
while(numKinds!=0){
int curNum=0;
do{
curNum=randomNumber(range);
}while(set.contains(curNum));
set.add(curNum);
numKinds--;
for(int i=0;i<m;i++){
arr[index++]=curNum;
}
}
for(int i=0;i<arr.length;i++){
int j=(int)(Math.random()*arr.length);
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
return arr;
}
public static int randomNumber(int range){
return (int)(Math.random()*range)-(int)(Math.random()*range);
}
public static void main(String[] args) {
int kinds=10;
int range=200;
int testTimes=1000000;
int max=9;
System.out.println("===========");
for(int i=0;i<testTimes;i++){
int a=(int)(Math.random()*max)+1;
int b=(int)(Math.random()*max)+1;
int k=Math.min(a,b);
int m=Math.max(a,b);
if(k==m){
m++;
}
int[] arr=randomArray(kinds,range,k,m);
int ans1=test(arr,k,m);
int ans2=onlyKTimes(arr,k,m);
if(ans1!=ans2){
System.out.println("************");
}
}
System.out.println("==============");
}
public static class TwoStacksQueue{
public Stack<Integer> stackPush;
public Stack<Integer> stackpop;
public TwoStacksQueue(){
stackPush=new Stack<Integer>();
stackpop=new Stack<Integer>();
}
private void pushToPop(){
while(!stackPush.empty()){
stackpop.push(stackPush.pop());
}
}
public void add(int pushInt){
stackPush.push(pushInt);
pushToPop();
}
public int poll(){
if(stackpop.empty()&&stackPush.empty()){
throw new RuntimeException("queue is empty");
}
pushToPop();
return stackpop.pop();
}
public int peek(){
if(stackpop.empty()&&stackPush.empty()){
throw new RuntimeException("queue is empty");
}
pushToPop();
return stackpop.peek();
}
public static class TwoQueueStack<T> {
public Queue<T> queue;
public Queue<T> help;
public TwoQueueStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(T value) {
queue.offer(value);
}
public T poll() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public T peek() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
help.offer(ans);
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
public static int getMax(int[] arr){
return process(arr,0,arr.length-1);
}
public static 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);
return Math.max(leftMax,rightMax);
}
public static int merge(int[] arr,int l,int m,int r){
int[] help=new int[r-l+1];
int i=help.length-1;
int p1=m;
int p2=r;
int res=0;
while(p1>=l&&p2>m){
res+=arr[p1]>arr[p2]?(p2-m):0;
help[i--]=arr[p1]>arr[p2]?arr[p1--]:arr[p2--];
}
while(p1>=l){
help[i--]=arr[p1--];
}
while(p2>m){
help[i--]=arr[p2--];
}
for(i=0;i<help.length;i++){
arr[l+i]=help[i];
}
return res;
}
public static int merge(int[] arr,int L,int M,int R){
int ans=0;
int windowR=M+1;
for(int i=L;i<=M;i++){
while(windowR<=R&&arr[i]>(arr[windowR]*2)){
windowR++;
}
ans+=windowR-M-1;
}
int[] help=new int[R-L+1];
int i=0;
int p1=L;
int p2=M+1;
while(p1<=M&&p2<=R){
help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=M){
help[i++]=arr[p1++];
}
while(p2<=R){
help[i++]=arr[p2++];
}
for(i=0;i<help.length;i++){
arr[L+i]=help[i];
}
return ans;
}
public static int countRangeSum(long[] nums,int lower,int upper){
if(nums==null||nums.length==0){
return 0;
}
long[] sum=new long[nums.length];
sum[0]=nums[0];
for(int i=1;i<nums.length;i++){
sum[i]=sum[i-1]+nums[i];
}
return count(sum,0,nums.length,lower,upper);
}
public static int count(long[] sum,int L,int R,int lower,int upper){
if(L==R){
if(sum[L]>=lower&&sum[L]<=upper){
return 1;
}
else return 0;
}
int mid=(L+R)/2;
int leftPart=count(sum,L,mid,lower,upper);
int rightPart=count(sum,mid+1,R,lower,upper);
int merge=merge(sum,L,mid,R,lower,upper);
return leftPart+rightPart+merge;
}
public static int merge(long[] arr,int L,int M,int R,int lower,int upper){
int ans=0;
int windowL=L;
int windowR=L;
for(int i=M+1;i<=R;i++){
long min=arr[i]-upper;
long max=arr[i]-lower;
while(windowR<=M&&arr[windowR]<=max){
windowR++;
}
while(windowL<=M&&arr[windowL]<min){
windowL++;
}
ans+=windowR-windowL;
}
long[] help=new long[R-L+1];
int i=0;
int p1=L;
int p2=M+1;
while(p1<=M&&p2<=R){
help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=M){
help[i++]=arr[p1++];
}
while(p2<=R){
help[i++]=arr[p2++];
}
for(i=0;i<arr.length;i++){
arr[L+i]=help[i];
}
return ans;
}
堆排序
public static void swap(int[] arr,int a,int b){
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void heapInsert(int[] arr,int index){
while(arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
public static void heapify(int[] arr,int index,int heapSize){
int left=index*2+1;
while(left<heapSize){
int largest=left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;
largest=arr[largest]>arr[index]?largest:index;
if(largest==index){
break;
}
swap(arr,largest,index);
index=largest;
left=index*2+1;
}
}
public static void heapSort(int[] arr){
if(arr==null||arr.length<2){
return;
}
for(int i=0;i<arr.length;i++){
heapInsert(arr,i);
}
int heapSize=arr.length;
swap(arr,0,--heapSize);
while(heapSize>0){
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
}
}
public static void sortedk(int[] arr,int k){
if(k==0) {
return;
}
PriorityQueue<Integer> heap=new PriorityQueue<>();
int index=0;
for(;index<=Math.min(arr.length-1,k);index++){
heap.add(arr[index]);
}
int i=0;
for(;index<arr.length;index++,i++){
heap.add(arr[index]);
arr[i]=heap.poll();
}
while(!heap.isEmpty()){
arr[i++]=heap.poll();
}
}