给定一个只包含0和1的大小为n的圆形数组，其中n=p*q（p和q都是奇数整数）。任务是检查是否存在一种方法，即在应用以下操作后，1将占多数：
null
- 将圆形阵列分成p个子阵列，每个子阵列的大小为q。
- 在每个子阵列中，占多数的数字将被存储到阵列B中。
- 现在，如果1在数组B中占多数，则称其为多数。
注： 如果某个数字的大小超过数组大小的一半，则该数字在数组中占多数。 例如：
输入： p=3，q=3，数组[]={0,0,1,1,0,1,1,0,0} 输出： 对 假设数组的索引从1到N，因为数组是圆形的，所以索引N和1将是相邻的。 按以下方式将此圆形阵列划分为子阵列：- {2,3,4}，{5,6,7}和{8,9,1}。[这些是元素索引] 在{2,3,4}中，1占多数， 在{5,6,7}中，1再次占多数，而 在{8,9,1}中，0占多数。 现在将1，1，0插入数组B，这样数组B={1，1，0} 在数组B中，1是多数元素，所以打印Yes。 输入： p=3，q=3，数组[]={1,0,0,1,1,0,0} 输出： 不 不管你如何划分这个圆形子阵列， 1不会占多数。因此，答案是否定的。
方法：
- 首先，迭代循环数组，并计算每个p子数组（大小为q）中1的总数。
- 将此数字存储到另一个数组（大小为p）中。
- 如果在这种情况下，1占多数，则打印“是”。
- 否则，通过移动前一个集合的索引1单位（增加或减少）来获取另一个集合，并仅跟踪给定集合中新的索引，并更新数组中的1个数。
- 重复第2步和第3步。
我们将重复q次，如果没有找到1的多数，直到找到为止，答案将是否定的，否则（如前一个示例中的情况）答案将是1。 因为在最大情况下，我们可以重复这个过程q次，每次我们只跟踪p子阵中的两个元素。 说明： 在给定的示例1中，我们将循环子数组划分为[索引]=>{1,2,3}，{4,5,6}，{7,8,9}，并存储另一个数组中的1的数量，这些数组在子数组中分别是[1,2,1]。 例1中的另一个集合增加1个单位，所以集合将是{2,3,4}，{5,6,7}，{8,9,1}。现在在集合1中，唯一的变化是包含元素4，删除元素1，我们将只跟踪这些，所以更新后的1的数量将是2,2,0。 以下是上述方法的实施情况：
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to check if 1 is the majority // element or not void majority( bool a[], int p, int q, int size) { // assuming starting and ending index of 1st subarray int start = 0, ends = q; // to store majority of p int arr[p]; // subarrays each of size q ; int k = 0; // Loop to calculate total number // of 1's in subarray which will get // stored in array arr[] while (k < p) { int one = 0; for ( int j = start; j < ends; j++) { if (a[j] == 1) { one++; } } // starting index of next subarray start = ends; // ending index of next subarray ends = ends + q; // storing 1's arr[k] = one; k++; } start = 0; ends = q; // variable to keep a check // if 1 is in majority or not bool found = 0; // In this case, we are repeating // the task of calculating // total number of 1's backward while (ends > 0) { // to store the total number of 1's int dist_one = 0; // Check if 1 is in majority in // this subarray for ( int i = 0; i < p; i++) if (arr[i] > q / 2) dist_one++; // If 1 is in majority return if (dist_one > p / 2) { found = 1; cout << "Yes" << endl; return ; } // shifting starting index of // subarray by 1 unit leftwards start--; // shifting ending index of // subarray by 1 unit leftwards ends--; // to ensure it is a valid index // ( array is circular) -1 index means // last index of a circular array if (start < 0) start = size + start; int st = start, en = ends, l = 0; // now to track changes occur // due to shifting of the subarray while (en < size) { if (a[st % size] != a[en % size]) { // st refers to starting index of // new subarray and en refers to // last element of same subarray // but in previous iteration if (a[st % size] == 1) arr[l]++; else arr[l]--; } l++; // now repeating the same // for other subarrays too st = (st + q); en = en + q; } } if (found == 0) { cout << "No" << endl; } } // Driver code int main() { int p = 3, q = 3; int n = p * q; bool a[] = { 0, 0, 1, 1, 0, 1, 1, 0, 0 }; // circular array of given size majority(a, p, q, n); return 0; } |
JAVA
// Java implementation of above approach import java.util.*; import java.lang.*; import java.io.*; class GFG { // Function to check if 1 is the majority // element or not static void majority( int a[], int p, int q, int size) { // assuming starting and ending index of 1st subarray int start = 0 , ends = q; // to store majority of p int []arr = new int [p]; // subarrays each of size q ; int k = 0 ; // Loop to calculate total number // of 1's in subarray which will get // stored in array arr[] while (k < p) { int one = 0 ; for ( int j = start; j < ends; j++) { if (a[j] == 1 ) { one++; } } // starting index of next subarray start = ends; // ending index of next subarray ends = ends + q; // storing 1's arr[k] = one; k++; } start = 0 ; ends = q; // variable to keep a check // if 1 is in majority or not boolean found = false ; // In this case, we are repeating // the task of calculating // total number of 1's backward while (ends > 0 ) { // to store the total number of 1's int dist_one = 0 ; // Check if 1 is in majority in // this subarray for ( int i = 0 ; i < p; i++) if (arr[i] > q / 2 ) dist_one++; // If 1 is in majority return if (dist_one > p / 2 ) { found = true ; System.out.println( "Yes" ); return ; } // shifting starting index of // subarray by 1 unit leftwards start--; // shifting ending index of // subarray by 1 unit leftwards ends--; // to ensure it is a valid index // ( array is circular) -1 index means // last index of a circular array if (start < 0 ) start = size + start; int st = start, en = ends,l = 0 ; // now to track changes occur // due to shifting of the subarray while (en < size) { if (a[st % size] != a[en % size]) { // st refers to starting index of // new subarray and en refers to // last element of same subarray // but in previous iteration if (a[st % size] == 1 ) arr[l]++; else arr[l]--; } l++; // now repeating the same // for other subarrays too st = (st + q); en = en + q; } } if (found == false ) { System.out.println( "No" ); } } // Driver code public static void main(String args[]) { int p = 3 , q = 3 ; int n = p * q; int a[] = { 0 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 0 }; // circular array of given size majority(a, p, q, n); } } |
Python3
# Python3 implementation of # above approach # Function to check if 1 is # the majority element or not def majority(a, p, q, size) : # assuming starting and # ending index of 1st subarray start = 0 ends = q # to store arr = [] arr = [ None ] * p # subarrays each of size q k = 0 # Loop to calculate total number # of 1's in subarray which # will get stored in array arr while (k < p): one = 0 for j in range (start, ends): if (a[j] = = 1 ): one = one + 1 # starting index of # next subarray start = ends # ending index of next # subarray ends = ends + q # storing 1's arr[k] = one k = k + 1 start = 0 ends = q # variable to keep a check # if 1 is in majority or not found = 0 # In this case, we are # repeating the task of # calculating total number # of 1's backward while (ends > 0 ) : # to store the total # number of 1's dist_one = 0 # Check if 1 is in majority # in this subarray for i in range ( 0 , p): if (arr[i] > q / 2 ): dist_one = dist_one + 1 # If 1 is in majority return if (dist_one > p / 2 ) : found = 1 print ( "Yes" ) return # shifting starting index of # subarray by 1 unit leftwards start = start - 1 # shifting ending index # of subarray by 1 unit # leftwards ends = ends - 1 # to ensure it is a valid # index( array is circular) -1 # index means last index of # a circular array if (start < 0 ): start = size + start st = start en = ends l = 0 # now to track changes occur # due to shifting of the # subarray while (en < size) : if (a[st % size] ! = a[en % size]) : # st refers to starting index of # new subarray and en refers to # last element of same subarray # but in previous iteration if (a[st % size] = = 1 ): arr[l] = arr[l] + 1 else : arr[l] = arr[l] - 1 l = l + 1 # now repeating the same # for other subarrays too st = (st + q) en = en + q if (found = = 0 ) : print ( "No" ) # Driver code p = 3 q = 3 n = p * q a = [ 0 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 0 ] # circular array of given size majority(a, p, q, n) # This code is contributed # by Yatin Gupta |
C#
// C# implementation of above approach using System; class GFG { // Function to check if 1 is the // majority element or not public static void majority( int [] a, int p, int q, int size) { // assuming starting and ending // index of 1st subarray int start = 0, ends = q; // to store majority of p int [] arr = new int [p]; // subarrays each of size q ; int k = 0; // Loop to calculate total number // of 1's in subarray which will // get stored in array arr[] while (k < p) { int one = 0; for ( int j = start; j < ends; j++) { if (a[j] == 1) { one++; } } // starting index of next subarray start = ends; // ending index of next subarray ends = ends + q; // storing 1's arr[k] = one; k++; } start = 0; ends = q; // variable to keep a check // if 1 is in majority or not bool found = false ; // In this case, we are repeating // the task of calculating // total number of 1's backward while (ends > 0) { // to store the total number of 1's int dist_one = 0; // Check if 1 is in majority in // this subarray for ( int i = 0; i < p; i++) { if (arr[i] > q / 2) { dist_one++; } } // If 1 is in majority return if (dist_one > p / 2) { found = true ; Console.WriteLine( "Yes" ); return ; } // shifting starting index of // subarray by 1 unit leftwards start--; // shifting ending index of // subarray by 1 unit leftwards ends--; // to ensure it is a valid index // ( array is circular) -1 index means // last index of a circular array if (start < 0) { start = size + start; } int st = start, en = ends, l = 0; // now to track changes occur // due to shifting of the subarray while (en < size) { if (a[st % size] != a[en % size]) { // st refers to starting index of // new subarray and en refers to // last element of same subarray // but in previous iteration if (a[st % size] == 1) { arr[l]++; } else { arr[l]--; } } l++; // now repeating the same // for other subarrays too st = (st + q); en = en + q; } } if (found == false ) { Console.WriteLine( "No" ); } } // Driver code public static void Main( string [] args) { int p = 3, q = 3; int n = p * q; int [] a = new int [] {0, 0, 1, 1, 0, 1, 1, 0, 0}; // circular array of given size majority(a, p, q, n); } } // This code is contributed by Shrikant13 |
PHP
<?php //PHP implementation of above approach // Function to check if 1 is the majority // element or not function majority( $a , $p , $q , $size ) { // assuming starting and ending index of 1st subarray $start = 0; $ends = $q ; // to store majority of p $arr = array (0); // subarrays each of size q ; $k = 0; // Loop to calculate total number // of 1's in subarray which will get // stored in array arr[] while ( $k < $p ) { $one = 0; for ( $j = $start ; $j < $ends ; $j ++) { if ( $a [ $j ] == 1) { $one ++; } } // starting index of next subarray $start = $ends ; // ending index of next subarray $ends = $ends + $q ; // storing 1's $arr [ $k ] = $one ; $k ++; } $start = 0; $ends = $q ; // variable to keep a check // if 1 is in majority or not $found = 0; // In this case, we are repeating // the task of calculating // total number of 1's backward while ( $ends > 0) { // to store the total number of 1's $dist_one = 0; // Check if 1 is in majority in // this subarray for ( $i = 0; $i < $p ; $i ++) if ( $arr [ $i ] > $q / 2) $dist_one ++; // If 1 is in majority return if ( $dist_one > $p / 2) { $found = 1; echo "Yes" , "" ; return ; } // shifting starting index of // subarray by 1 unit leftwards $start --; // shifting ending index of // subarray by 1 unit leftwards $ends --; // to ensure it is a valid index // ( array is circular) -1 index means // last index of a circular array if ( $start < 0) $start = $size + $start ; $st = $start ; $en = $ends ; $l = 0; // now to track changes occur // due to shifting of the subarray while ( $en < $size ) { if ( $a [ $st % $size ] != $a [ $en % $size ]) { // st refers to starting index of // new subarray and en refers to // last element of same subarray // but in previous iteration if ( $a [ $st % $size ] == 1) $arr [ $l ]++; else $arr [ $l ]--; } $l ++; // now repeating the same // for other subarrays too $st = ( $st + $q ); $en = $en + $q ; } } if ( $found == 0) { echo "No" , "" ; } } // Driver code $p = 3; $q = 3; $n = $p * $q ; $a = array ( 0, 0, 1, 1, 0, 1, 1, 0, 0 ); // circular array of given size majority( $a , $p , $q , $n ); #This Code is Contributed by ajit ?> |
Javascript
<script> // Javascript implementation // of above approach // Function to check if 1 is the // majority element or not function majority(a, p, q, size) { // assuming starting and ending // index of 1st subarray let start = 0, ends = q; // to store majority of p let arr = new Array(p); arr.fill(0); // subarrays each of size q ; let k = 0; // Loop to calculate total number // of 1's in subarray which will // get stored in array arr[] while (k < p) { let one = 0; for (let j = start; j < ends; j++) { if (a[j] == 1) { one++; } } // starting index of next subarray start = ends; // ending index of next subarray ends = ends + q; // storing 1's arr[k] = one; k++; } start = 0; ends = q; // variable to keep a check // if 1 is in majority or not let found = false ; // In this case, we are repeating // the task of calculating // total number of 1's backward while (ends > 0) { // to store the total number of 1's let dist_one = 0; // Check if 1 is in majority in // this subarray for (let i = 0; i < p; i++) { if (arr[i] > parseInt(q / 2, 10)) { dist_one++; } } // If 1 is in majority return if (dist_one > parseInt(p / 2, 10)) { found = true ; document.write( "Yes" ); return ; } // shifting starting index of // subarray by 1 unit leftwards start--; // shifting ending index of // subarray by 1 unit leftwards ends--; // to ensure it is a valid index // ( array is circular) -1 index means // last index of a circular array if (start < 0) { start = size + start; } let st = start, en = ends, l = 0; // now to track changes occur // due to shifting of the subarray while (en < size) { if (a[st % size] != a[en % size]) { // st refers to starting index of // new subarray and en refers to // last element of same subarray // but in previous iteration if (a[st % size] == 1) { arr[l]++; } else { arr[l]--; } } l++; // now repeating the same // for other subarrays too st = (st + q); en = en + q; } } if (found == false ) { document.write( "No" ); } } let p = 3, q = 3; let n = p * q; let a = [0, 0, 1, 1, 0, 1, 1, 0, 0]; // circular array of given size majority(a, p, q, n); </script> |
输出：
Yes
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
