一个数组a[],有N个元素,允许重复,如果其一半以上的内容等于v,则称其“主要包含一个v元素”。给定数组a[],旨在得出一个高效的算法(在时间 N.log (N) 并使用分而治之)检查它是否包含多数元素并确定它。考虑数组元素之间唯一可用的比较操作,是等式 (a [i] == a [j]),在恒定时间内执行。 (提示:在算法中,把数组to[]分成两个子数组a1[]和a2[],每个子数组的大小都是a[]的一半。如果a[]中大部分的元素是v,那么v一定是也是 a1 [] 或 a2 [] 或两者中多数的元素。
int main() {
int a[12] = {5, 9, 3, 13, 5, 21, 5, 7, 17, 12, 5, 6};
int N = 12, lo = 0, hi = N - 1, mid,i,j;
mid = lo + (hi - lo) / 2;
int n1 = mid - lo + 1;
int n2 = hi - mid;
int a1[n1],a2[n2];
/* Copy data to temp arrays a1[] and a2[] */
for (i = 0; i < n1; i++)
a1[i] = a[lo + i];
for (j = 0; j < n2; j++)
a2[j] = a[mid+1+j];
while (i < n1 && j < n2) {
if(a1[i]==a2[j]){
}else if(){
}else{
}
}
return 0;
}
我在使用相等操作比较辅助数组以查看最多元素是在 a1[] 还是 a2[] 或两者上时遇到了麻烦!
最佳答案
这是符合描述的 Python 实现(抱歉,我不精通 C,但我认为它是非常简单的代码)。我们可以跟踪所检查的每个部分的记录返回值和索引,以了解其工作原理。
# Returns v if v is a majority;
# otherwise, returns None
def f(arr, low, high):
if low == high:
return arr[low]
if low + 1 == high:
return arr[low] if arr[low] == arr[high] else None
n = high - low + 1
mid = (low + high) / 2
l = f(arr, low, mid)
r = f(arr, mid + 1, high)
print 'n: ' + str(n) + '; l: ' + str(l) + '; r: ' + str(r) + '; L: ' + str((low, mid)) + '; R: ' + str((mid + 1, high))
if l == r:
return l
counts = [0, 0]
for i in xrange(low, high + 1):
if arr[i] == l:
counts[0] = counts[0] + 1
if arr[i] == r:
counts[1] = counts[1] + 1
if l and counts[0] * 2 > n:
return l
if r and counts[1] * 2 > n:
return r
return None
输出:
a = [5, 9, 3, 5, 5, 21, 5, 7, 17, 5, 5, 5]
print f(a, 0, len(a) - 1)
"""
n: 3; l: None; r: 3; L: (0, 1); R: (2, 2)
n: 3; l: 5; r: 21; L: (3, 4); R: (5, 5)
n: 6; l: None; r: 5; L: (0, 2); R: (3, 5)
n: 3; l: None; r: 17; L: (6, 7); R: (8, 8)
n: 3; l: 5; r: 5; L: (9, 10); R: (11, 11)
n: 6; l: None; r: 5; L: (6, 8); R: (9, 11)
n: 12; l: None; r: 5; L: (0, 5); R: (6, 11)
5
"""
关于c - 数组中的大多数元素分而治之 O(N.log(N)),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48583034/