Thuật toán để tìm số cao/thấp với tối đa 1.5n so sánh

Question

Tôi đã suy nghĩ về câu hỏi bài tập về nhà này một chút ngay bây giờ. Với một mảng số có kích thước n, thiết kế một thuật toán sẽ tìm thấy các giá trị cao và thấp với hầu hết các so sánh 1.5n.

thử đầu tiên của tôi là

int high=0 
int low= Number.MaxValue //problem statement is unclear on what type of number to use 
Number numList[0 . . n] //number array, assuming unsorted 

for (i=0, i < n, i++) { 
    if (numList[i] > high) 
    high = numList[i] 

    else if (numList[i] < low) 
    low = numList[i] 

} 

Vấn đề của tôi là mỗi lần lặp của vòng lặp có một trong ba khả năng:

• giá trị thấp được tìm thấy - 1 so sánh làm
• giá trị cao được tìm thấy - 2 so sánh được thực hiện
• không tìm thấy - 2 so sánh được thực hiện

Vì vậy, đối với toàn bộ mảng truyền tải, có thể thực hiện tối đa các phép so sánh 2n, đây là một sự khác biệt lớn so với yêu cầu tối đa của vấn đề là 1,5 so sánh.

Answer 1

Bắt đầu với một cặp số và tìm số phút tối thiểu và địa phương tối đa (so sánh n/2). Tiếp theo, tìm giá trị tối đa toàn cầu từ n/2 giá trị cực đại cục bộ (so sánh n/2) và min toàn cục tương tự từ phút địa phương (so sánh n/2). Tổng số so sánh: 3 * n/2!

For i in 0 to n/2: #n/2 comparisons 
    if x[2*i]>x[2*i+1]: 
     swap(x,2*i,2*i+1) 

global_min = min(x[0], x[2], ...) # n/2 comparisons 
global_max = max(x[1], x[3], ...) # n/2 comparisons 

Lưu ý rằng giải pháp trên thay đổi mảng. Giải pháp thay thế:

Initialize min and max 
For i = 0 to n/2: 
    if x[2*i]<x[2*i+1]: 
     if x[2*i]< min: 
      min = x[2*i] 
     if x[2*i+1]> max: 
      max = x[2*i+1] 
    else: 
     if x[2*i+1]< min: 
      min = x[2*i+1] 
     if x[2*i]> max: 
      max = x[2*i] 

Answer 2

Đây là câu trả lời tương tự như ElKamina nhưng tôi đã bắt đầu viết mã giả tôi nghĩ mình đã kết thúc và đăng.

Ý tưởng là so sánh cặp giá trị (n/2 so sánh) để nhận được một mảng giá trị cao và một mảng giá trị thấp. Với mỗi mảng, chúng ta lại so sánh cặp giá trị (so sánh 2 * n/2) để có được giá trị cao nhất và thấp nhất tương ứng.

n/2 + 2*n/2 = 1.5n comparisons 

Đây là giả:

int[] highNumList; 
int[] lowNumList; 

for (i = 0, i < n, i+=2) 
{ 
    a = numList[i]; 
    b = numList[i+1]; 
    if (a > b) 
    { 
     highNumList.Add(a); 
     lowNumlist.Add(b); 
    } 
    else 
    { 
     highNumlist.Add(b); 
     lowNumList.Add(a); 
    } 
} 

int high = highNumList[0]; 
int low = lowNumList[0]; 

for (i = 0, i < n/2, i+=2) 
{ 
    if (highNumList[i] < highNumList[i+1]) 
     high = highNumList[i+1] 
    if (lowNumList[i] > lowNumList[i+1]) 
     low = lowNumList[i+1] 
} 

Mã này không chiếm n không phải là chẵn hoặc mảng ban đầu là rỗng.

Answer 3

Đây là câu hỏi tôi có trong một cuộc phỏng vấn và tôi đã tìm thấy câu trả lời với một gợi ý nhỏ từ người phỏng vấn là "Bạn so sánh hai con số như thế nào?" (nó thực sự đã giúp).

Dưới đây là lời giải thích:

phép nói rằng tôi có 100 số (bạn có thể dễ dàng thay thế nó bằng n nhưng nó hoạt động tốt hơn ví dụ như nếu n là một số chẵn). Những gì tôi làm là tôi chia nó thành 50 danh sách gồm 2 con số. Đối với mỗi cặp vợ chồng, tôi thực hiện một so sánh và tôi đã thực hiện (so sánh 50 so với bây giờ), sau đó tôi chỉ cần tìm mức tối thiểu (tối thiểu là 49 so sánh) và tối đa tối đa (cũng là 49 so sánh)) như vậy mà chúng ta phải thực hiện 49 + 49 + 50 = 148 so sánh. Đã được thực hiện !

Ghi chú: để tìm ra tối thiểu chúng tôi tiến hành như sau (trong mã giả):

n=myList.size(); 
    min=myList[0]; 
    for (int i(1);i<n-1;i++) 
    { 
    if (min>myList[i]) min=myList[i]; 
    } 
    return min; 

Và chúng tôi tìm thấy nó trong (n-1) so sánh.Mã này gần như giống nhau cho tối đa.

Answer 4

Tôi biết điều này đã được trả lời, nhưng trong trường hợp ai đó đang tìm cách khác để suy nghĩ về điều này. Câu trả lời này tương tự như Lester's, nhưng có thể xử lý các giá trị lẻ của n mà không vi phạm và vẫn sẽ tạo ra tối đa 1.5n so sánh. Bí mật nằm trong modulus. ;)

Là tác dụng phụ của việc đảm bảo chúng tôi đặt giá trị cuối cùng trong mảng phụ phù hợp, phần tử thứ hai trong danh sách đã cho sẽ được so sánh và đặt hai lần. Tuy nhiên, vì chúng tôi không thay đổi mảng ban đầu và chúng tôi chỉ quan tâm đến mức cao và thấp của bộ này, điều này không thực sự tạo nên sự khác biệt.

Initialize lowArray and highArray 
Initialize subArrayCounter to 0 

For i = 0; i < n; i+=2 
    X = givenList[i]; 
    Y = givenList[(i+1)%n]; 
    If(x < y) 
     lowArray[subArrayCounter] = x; 
     highArray[subArrayCounter] = y; 
     subArrayCounter++; 
    else 
     lowArray[subArrayCounter] = y; 
     highArray[subArrayCounter] = x; 
     subArrayCounter++; 

Initialize low to lowArray[0]; 
Initialize high to highArray[0]; 

For i = 1; i < lowArray.length; i++ 
    If(lowArray[i] < low) 
     Low = lowArray[i]; 

For i = 1; i < highArray.length; i++ 
    If(highArray[i] > high) 
     High = highArray[i]