한 배열 에서 최대 최소 수 를 동시에 찾 아 라. - 알고리즘 서론 9 장.

(1) 우선 한 배열 에서 최대 또는 최소 값 을 찾 아 한 번 만 옮 겨 다 니 며 n - 1 번 비교 하면 얻 을 수 있다.

for(int i=0;ilength;i++){
if(min>array[i]){
min=array[i];
}

(2) 최대 최소 치 를 동시에 꺼 내 는 것 은 한 번 만 옮 겨 다 니 는 것 을 의미한다.
실제로 기껏해야 3 * n / 2 번 이면 됩 니 다. 요 소 를 쌍 으로 처리 할 수 있 습 니 다. 먼저 각 쌍 의 크기 를 비교 한 다음 에 큰 것 과 최대 치 를 비교 하고 작은 것 과 최소 치 를 비교 할 수 있 습 니 다.패 리 티: 홀수 개: 최대 와 최소 값 을 첫 번 째 값 짝수 개 로 설정 합 니 다. 최대 와 최소 값 을 각각 앞의 두 개 로 설정 합 니 다.사실 남 은 게 짝수 라 는 걸 보증 해 야 돼 요.

public void getMax_Min(int a[]){
        int len=a.length;
        int max=0,min=0;
        int i=0,j=len-1;
        if(len%2==0){
            if(a[0]>a[1])
            {   max=a[0];
                min=a[1];
            }
            else{
                max=a[1];
                min=a[0];
            }
            i=2;//   2  
        }
        else{
            max=a[0];
            min=a[0];
            i=1;
        }

        while(iif(a[i]max=a[j]>max?a[j]:max;
min=a[i]<min?a[i]:min;
}
else{
max=a[i]>max?a[i]:max;
min=a[j]<min?a[j]:min;
}
i++;
j--;
}
System.out.println(max+"   "+min);
}

선형 시간 내 에 배열 a 의 i 작은 (또는 큰) 요 소 를 구하 고 작은 것 을 예 로 들 면:

public int  getRandom_select(int a[],int start,int end,int i){
        if(start==end){
            return a[start];
        }
        int q=Partition(a,start,end);
        //System.out.println("q"+q+"start"+start+"i"+i);
        if((q-start+1)==i){//       q-start+1,     q,  i,    ， q    0——a.length        ，    k
            //System.out.println("q"+q+"  "+i);
            return a[q];
        }
        int k=q-start+1;//     start q      
        if(k>i)
            return getRandom_select(a,start,q-1,i);
        else {
            return getRandom_select(a,q+1,end,i-k);
        }
    }


    int Partition(int a[],int left,int right)//       ，         
    {
        int i=left;
        int j=right;
        int temp=a[left];
        System.out.println("temp"+temp);
        while(iwhile(i=temp)
                j--;
                if(iwhile(iif(ireturn i;
    }

평균 적 인 상황 에서 시간 복잡 도 는 o (n) 이 고 최 악의 경 우 는 매번 남 은 요소 가 가장 큰 것 으로 나 뉘 는 것 이 o (n ^ 2) 이다.
* 5 번 째 작은 0, 8, 5, 2, 4, 6, 19, 23 20 을 취하 여 처음으로 Start = 0, end = 9 로 구분한다.q = 0 얻 기;,구분 후 배열 8, 5, 2, 4, 6, 3, 19, 23, 20 의 결 과 는 a [1] = 8 부터 시작 되 는데 이때 4 번 째 로 작 아야 하기 때문에 비교 할 때 반드시 q - (현재 의) start + 1 * * * *