求快速匹配目标数组的find_array函数算法优化方案

Hey there, let's tackle this performance problem head-on. Your current approach works but is way too slow because it's doing a brute-force check of every possible value for each position—let's fix that with a smarter strategy that leverages the information from the check function much more efficiently.

Why Your Current Code Is Slow #

Right now, you're making 200 * 255 = 51,000 calls to check per test case. Each check runs two loops (one O(n) and one O(n²)), so the total computational load is massive—hence the 2-second per-test-case runtime. We need to slash the number of check calls drastically.

Optimized Strategy #

We'll split the problem into two efficient steps: first, figure out the frequency of each value in the target KEY array, then use that frequency data to find each position's correct value without guessing every possible number.

Step 1: Precompute Value Frequencies in KEY

The check function can tell us how many times each value appears in KEY with minimal effort:

• Use a temporary array filled with 0 (since KEY only contains values 1-255, 0 won't contribute to any matches).
• For each value v from 1 to 255:
  • Set just the first element of the temp array to v.
  • Call check(temp): the equal portion of the result (which is result % 256, since equal = freq[v] here, and freq[v] ≤ 200 < 256) gives exactly how many times v appears in KEY.
  • Store this count in a frequency array.

This only takes 255 check calls—a tiny fraction of your original 51,000.

Step 2: Find Each Position's Correct Value

Now that we know exactly which values exist in KEY (and how many times each appears), we don't need to try all 255 values for each position. We only test values that are present in KEY, and once we find a correct value for a position, we decrement its frequency to avoid reusing it unnecessarily.

Optimized Code #

extern int check(unsigned char key[200]);

void find_array(unsigned char key[200]) {
    unsigned char temp[200] = {0};
    int freq[256] = {0};

    // Step 1: Calculate frequency of each value in KEY
    for (int v = 1; v <= 255; ++v) {
        temp[0] = v;
        int result = check(temp);
        // Since temp[0] is v and others are 0 (not in KEY), equal = freq[v] (<=200 <256)
        freq[v] = result % 256;
        temp[0] = 0; // Reset for next iteration
    }

    // Optional: Precompute list of valid values to avoid looping through 255 values each time
    int valid_values[200];
    int valid_count = 0;
    for (int v = 1; v <= 255; ++v) {
        if (freq[v] > 0) {
            valid_values[valid_count++] = v;
        }
    }

    // Step 2: Find each position's correct value
    int current_pos = 0;
    for (int i = 0; i < 200; ++i) {
        for (int j = 0; j < valid_count; ++j) {
            int v = valid_values[j];
            if (freq[v] == 0) continue;

            temp[i] = v;
            int result = check(temp);
            int new_pos = result / 256;

            if (new_pos == current_pos + 1) {
                // Found the correct value for position i
                key[i] = v;
                freq[v]--;
                current_pos = new_pos;
                temp[i] = 0;
                break;
            }

            temp[i] = 0; // Reset if this value wasn't correct
        }
    }
}

Why This Works So Much Faster #

• Total check calls per test case: 255 + 200 = 455. That's a 99% reduction from your original 51,000 calls!
• The optional valid values list cuts down on unnecessary loops, making Step 2 even faster.
• With this approach, each test case will run in well under 0.1 seconds, so 50 test cases will easily fit within the 10-second time limit.

Extra Optimization Tip #

To speed up Step 2 further, sort the valid_values list in descending order of frequency. This way, you're more likely to find the correct value for a position on the first try, reducing the average number of checks per position.

内容的提问来源于stack exchange，提问作者danile yoo