arrays - 找到 S(S=(min2∧min) ) 的最大可能值，其中 min2 和 min 是数组的 k 个元素中的最小整数和下一个最小整数

Question

我正在处理一个编程问题。问题如下:

给定一个包含 N 个不同元素的数组 A[]。令 min2 和 min 为区间 [L,R] 中的最小和下一个最小元素，其中 1 ≤⟩L < R ≤ N。

S=(min2 ∧min).

其中 ∧ 是按位异或运算符。 我必须找到 S 的最大可能值。

我已经写了 1 个解决方案来找到 S 的最大可能值，但它的复杂性很高。我在想是否可以对其进行优化。由于甚至元素的范围 k 也不固定，我必须计算所有范围，即 k = 2 到数组的长度。 我采用的方法是先取k为2，从第0个元素开始，在前k个元素中找到min&min2，计算S，如果大于前面的S，就把这个作为S，否则忽略。从第一个元素开始，我在接下来的 k 个元素中找到 min 等等。与其他更高范围相同，即 3、4、5... 以下是我编写的代码:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {

    int num = 0, S = Integer.MIN_VALUE, min = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
    int[] input = null;

    try {
        BufferedReader bufferRead = new BufferedReader(new InputStreamReader(System.in));
        String s = bufferRead.readLine();
        num = Integer.parseInt(s);
        s = bufferRead.readLine();
        String arr[] = s.split(" ");

        input = new int[arr.length];
        for(int i =0; i<arr.length;i++) {
            input[i] = Integer.parseInt(arr[i]);
        }
    }
    catch(IOException e)
    {
        e.printStackTrace();
    }



    for(int k=2;k<=input.length;k++) {
         int j =0;

         while(j<input.length-k+1)
             {

             int i=j;

             for(i=j;i<(j+k);i++)
             {
             if(input[i] < min)
                 {
                 min2 = min;
                 min = input[i];
             }
                 else if(input[i] > min && input[i] < min2)
                 {
                 min2 = input[i];

             }


         }

         int st = (((min2 & min)^(min2 | min)) & (min2 ^ min));


         if(st > S)
             S = st;
            j++;
            min = Integer.MAX_VALUE;
            min2 = Integer.MAX_VALUE;
         }

        }
        System.out.println( S );

    }

}

这能以某种方式优化吗？

Answer 1

这可以用线性时间 O(N) 空间算法来完成。

为了使事情更简单，在第二小的元素出现在最小的元素之后的情况下执行此操作。然后反转数组并再次执行(或者只是从最后一个元素开始向后处理数组)。

使用数组的每个元素作为区间最右边的元素 (A[R])。现在，唯一被视为区间 (A[L]) 最左边元素的元素是小于 A[R] 的最近元素(如果有的话)。 A[L], A[R] 是这个区间的两个最小元素，因此计算它们的 S 并在必要时更新结果。并且可以使用堆栈找到最近的较小元素。

伪代码:

result = -infinity
for each X in array A:
    while NOT stack.empty AND stack.top > X: stack.pop
    if NOT stack.empty:
        result = max(result, X XOR stack.top)
    stack.push(X)
reverse array A and repeat

证明:该算法(确切地说，它的前半部分)尝试将数组的每个元素作为某个区间的第二小元素，使得(第一)最小元素位于它的左侧。显然，这考虑了区间 A[L]..A[R]。此外，如果我们将此间隔扩展到任一侧(或两侧)并且此扩展间隔的所有其他元素都大于 A[R]，则 A[R] 仍然是第二小的元素，算法也会考虑这个区间(但不会改变S的最优值)。如果至少有一个额外的元素小于 A[R] 或者不是扩展，我们开始缩小区间，A[R] 不再是第二小的元素，所以在这个特定的迭代中不考虑这样的间隔(但是当我们尝试将某个其他元素作为第二大元素或者当我们期望当前元素右侧的第一大元素时考虑)。