给定一个整数数组，任务是找到大小为K的子数组的最大异或值。 例如：
null
Input : arr[] = {2, 5, 8 ,1 , 1 ,3} k = 3Output : 15Explanation : All subarrays of size k (=3) and their XOR values are: {2, 5, 8} => XOR value = 15 {5, 8, 1} => XOR value = 12 {8, 1, 1} => XOR value = 8 {1, 1, 3} => XOR value = 3Maximum of all XOR values = 15Input : arr[] = {1, 2, 4, 5, 6}Output : 6
A. 简单解决方案 是一个一个地考虑大小k的所有子数组，并计算XOR值。最后返回所有XOR值的最大值。这个解决方案需要O（n*k）时间 一 有效解决方案 花了很多时间。这个想法很简单，我们可以通过移除前一个子阵的第一个元素并添加当前子阵的最后一个元素来找到大小为k的当前子阵的异或值。我们可以通过再次执行XOR来从当前XOR中删除一个元素，因为XOR的属性是a^x^x=a。 算法：
Let input array be 'arr[]' and size of array be 'n'max_xor ; // user to store maximum xor valuecurrent_xor; // user to store xor value of current subarray // of size k // First compute xor value of first subarray of size k // (i goes from 0 to k)corrent_xor = current_xor ^ arr[i] // Initialize maximum XORmax_xor = current_xor Traversal rest array (i goes from k to n-1 ) a). remove first element of previous subarray current_xor = current_xor ^ arr[i-k] b). add new element to subarray current_xor = current_xor ^ arr[i] c). update max_xor = max(max_xor, current_xor) return max_xor
以下是上述步骤的实施情况。
C++
// C++/C program to find maximum xor value of subarray of // size k #include<iostream> using namespace std; // Returns maximum XOR value of subarray of size k int maximumXOR( int arr[] , int n , int k) { // Compute XOR value of first subarray of size k int current_xor = 0 ; for ( int i = 0 ; i < k ; i++) current_xor = current_xor ^ arr[i]; // Traverse rest of the array int max_xor = current_xor; for ( int i = k ; i < n; i++) { // First remove previous subarray's first // element current_xor = current_xor ^ arr[i-k]; // add new element current_xor = current_xor ^ arr[i]; // Update maximum xor value max_xor = max(max_xor, current_xor); } return max_xor; } // Driver program int main() { int arr[] = {2, 5, 8 ,1 , 1 ,3} ; int k = 3; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Maximum XOR : " << maximumXOR(arr, n, k); return 0; } |
JAVA
// Java program to find maximum xor value of // subarray of size k import java.io.*; class GFG { // Returns maximum XOR value of subarray of size k static int maximumXOR( int arr[] , int n , int k) { // Compute XOR value of first subarray of size k int current_xor = 0 ; for ( int i = 0 ; i < k ; i++) current_xor = current_xor ^ arr[i]; // Traverse rest of the array int max_xor = current_xor; for ( int i = k ; i < n; i++) { // First remove previous subarray's first // element current_xor = current_xor ^ arr[i-k]; // add new element current_xor = current_xor ^ arr[i]; // Update maximum xor value max_xor = Math.max(max_xor, current_xor); } return max_xor; } // Driver program public static void main (String[] args) { int arr[] = { 2 , 5 , 8 , 1 , 1 , 3 } ; int k = 3 ; int n = arr.length; System.out.println( "Maximum XOR : " + maximumXOR(arr, n, k)); } } // This code is contributed by anuj_67. |
Python 3
# Python3 program to find maximum # xor value of subarray of # size # Returns maximum XOR value # of subarray of size k def maximumXOR(arr , n , k): # Compute XOR value of first # subarray of size k current_xor = 0 for i in range ( k): current_xor = current_xor ^ arr[i] # Traverse rest of the array max_xor = current_xor for i in range ( k,n): # First remove previous subarray's first # element current_xor = current_xor ^ arr[i - k] # add new element current_xor = current_xor ^ arr[i] # Update maximum xor value max_xor = max (max_xor, current_xor) return max_xor # Driver program if __name__ = = "__main__" : arr = [ 2 , 5 , 8 , 1 , 1 , 3 ] k = 3 n = len (arr) print ( "Maximum XOR : " ,maximumXOR(arr, n, k)) # This code is contributed by # ChitraNayal |
C#
// C# program to find maximum // xor value of subarray of // size k using System; class GFG { // Returns maximum XOR value // of subarray of size k static int maximumXOR( int []arr, int n, int k) { // Compute XOR value of first // subarray of size k int current_xor = 0 ; for ( int i = 0; i < k; i++) current_xor = current_xor ^ arr[i]; // Traverse rest of the array int max_xor = current_xor; for ( int i = k ; i < n; i++) { // First remove previous // subarray's first // element current_xor = current_xor ^ arr[i-k]; // add new element current_xor = current_xor ^ arr[i]; // Update maximum xor value max_xor = Math.Max(max_xor, current_xor); } return max_xor; } // Driver Code public static void Main () { int []arr = {2, 5, 8 ,1 , 1 ,3} ; int k = 3; int n = arr.Length; Console.WriteLine( "Maximum XOR : " + maximumXOR(arr, n, k)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to find maximum // xor value of subarray of size k // Returns maximum XOR value // of subarray of size k function maximumXOR( $arr , $n , $k ) { // Compute XOR value of // first subarray of size k $current_xor = 0 ; for ( $i = 0 ; $i < $k ; $i ++) $current_xor = $current_xor ^ $arr [ $i ]; // Traverse rest of the array $max_xor = $current_xor ; for ( $i = $k ; $i < $n ; $i ++) { // First remove previous // subarray's first element $current_xor = $current_xor ^ $arr [ $i - $k ]; // add new element $current_xor = $current_xor ^ $arr [ $i ]; // Update maximum xor value $max_xor = max( $max_xor , $current_xor ); } return $max_xor ; } // Driver Code $arr = array (2, 5, 8, 1, 1, 3) ; $k = 3; $n = sizeof( $arr ); echo "Maximum XOR : " , maximumXOR( $arr , $n , $k ); // This code is contributed by m_kit ?> |
Javascript
<script> // Javascript program to find maximum xor value of // subarray of size k // Returns maximum XOR value of subarray of size k function maximumXOR(arr,n,k) { // Compute XOR value of first subarray of size k let current_xor = 0 ; for (let i = 0 ; i < k ; i++) current_xor = current_xor ^ arr[i]; // Traverse rest of the array let max_xor = current_xor; for (let i = k ; i < n; i++) { // First remove previous subarray's first // element current_xor = current_xor ^ arr[i-k]; // add new element current_xor = current_xor ^ arr[i]; // Update maximum xor value max_xor = Math.max(max_xor, current_xor); } return max_xor; } // Driver program let arr=[2, 5, 8 ,1 , 1 ,3]; let k = 3; let n = arr.length; document.write( "Maximum XOR : " + maximumXOR(arr, n, k)); // This code is contributed by rag2127 </script> |
输出：
Maximum XOR : 15
时间复杂性： O（n） 本文由 尼桑特·辛格（平图） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
