算法大挑战
请编写以下函数 int MajorityElement(int array[],int n);
该函数返回数组array中的多数元素。多数元素是指在占绝对多数（至少51%）的一个值。如果多数元素不存在，那么返回常量NoMajorityElement,该函数必须满足下面的条件：
1. 必须以O(N)时间运行。
2. 必须使用O（1）的附加空间。换句话说，可用个别的临时变量，而不可以使用任何的临时数组。并且不能使用递归解决，这是因为随着递归层数加深，会需要空间来存储栈帧。
3. 不能改变数组中的任何元素的值。
大家一起讨论下啦
[解决办法]
- C# code
using System;using System.Collections.Generic;using System.Text;using System.Collections;namespace 算法大挑战{ class Program { public ArrayList arr = new ArrayList(); private int MajorityElement(int[] array,int n) { int count = 0; int num = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((array[i]^array[j])==0) { count++; if ((double)(count / 8) > 0.5) { num = array[i]; } } } } return num; } static void Main(string[] args) { int[] array ={2,2,3,4,2,5,3,2,2,2}; int n = array.Length; Program p = new Program(); int num = p.MajorityElement(array,n); Console.WriteLine("{0}",num); Console.ReadKey(); } }}
[解决办法]
如过数组是有序的，我的思路如下：
- C# code
int MajorityElement(int array[],int n){int NoMajorityElement=-1;int len=array[].length;int n=array[0];int num=0;for(int i=1;i<len;i++){if(array[i]=n){num++;float fl=num/len;if(fl>= o.51){retrun n;break;}}else{n=array[i];num=0;}if(i=m){return NoMajorityElement;}}
[解决办法]
让我走走诡异路线：
- C# code
using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Text.RegularExpressions;namespace ConsoleApplication2{ class Program { static int MajorityElement(int[] array, int n) { string s = ""; Array.Sort(array); for (int i = 0; i < array.Length; i++) s += array[i]; int iTemp = 0; int iMax = 0; MatchCollection mc = Regex.Matches(s, @"(\d)\1+"); foreach (Match m in mc) { iTemp = m.Value.Length; if (iMax < iTemp) { iMax = iTemp; n = Convert.ToInt32(m.Value[0].ToString()); } } if (iMax > array.Length / 2) return n; return -1; } static void Main(string[] args) { int[] array = { 2, 2, 3, 4, 2, 5, 3, 2, 2, 2 }; int n = array.Length; int num = MajorityElement(array, n); Console.WriteLine("{0}", num); Console.ReadKey(); } }}
[解决办法]
public find(int[] arr){ //只有当某一元素在数组中的绝对数超过50%，函数才能返回最多数。 int ele=0;
int rud=0;
foreach(int n in arr)
{
if(rud==0)
{
ele=n;
rud=1;
}
else if(ele==n)
{
rud++;
}
else
{
rud--;
}
}
if(rud>0) return ele
return 0;
}
------解决方案--------------------
- C/C++ code
有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来.#include <stdio.h>int num[1000000];int FindMainElement(int array[], int n){ int curr, i; for (curr = 0, i = 0; n > 1; n = curr) { for (i = curr = 0; i < n - 1; i += 2) array[i] == array[i+1] ? array[curr++] = array[i] : 0; i==n-1 ? array[curr++] = array[n-1] : 0; } return array[0];}int main(void){ int n, i; while (scanf("%d", &n) == 1) { for (i = 0; i < n; ++i) scanf("%d", num+i); printf("%d\n", FindMainElement(num, n)); } return 0;}有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=1000000).#include <stdio.h>static int num[1000000];static int num1[1000000];int FindMainElement(int array[], int n){ int curr, i, total = n; if (total % 2 == 0) { for (curr = 0, i = 0; n > 2; n = curr) { for (i = curr = 0; i < n - 1; i += 2) array[i] == array[i+1] ? array[curr++] = array[i] : 0; i==n-1 ? array[curr++] = array[n-1] : 0; } int a = array[0], b = array[1], cnt = 0; for (i = 0; i < total; ++i) if (num1[i] == a) ++cnt; if (cnt >= total/2) return a; else return b; } else { for (curr = 0, i = 0; n > 1; n = curr) { for (i = curr = 0; i < n - 1; i += 2) array[i] == array[i+1] ? array[curr++] = array[i] : 0; i==n-1 ? array[curr++] = array[n-1] : 0; } return array[0]; }}int main(void){ int n, i, value; char t; while (scanf("%d\n", &n) == 1) { for (i = 0; i < n - 1; ++i) { value = 0; while ((t = getchar()) != ' ') value = value * 10 + t - '0'; num1[i] = num[i] = value; } value = 0; while ((t = getchar()) != '\n') value = value * 10 + t - '0'; num1[i] = num[i] = value; printf("%d\n", FindMainElement(num, n)); } return 0;}
[解决办法]
- C# code
static void QuickSort(int[] a,int start,int end){ int i=start,j=end; int pivot = a[i]; while(i<j) { while(i<j && pivot<=a[j]) j--; a[i] = a[j]; while(i<j && a[i]<=pivot) i++; a[j]=a[i]; } a[i] = pivot; if(i>start) QuickSort(a,start,i); if(i<end) QuickSort(a,i+1,end);}
[解决办法]
请编写以下函数 int MajorityElement(int array[],int n);
该函数返回数组array中的多数元素。多数元素是指在占绝对多数（至少51%）的一个值。如果多数元素不存在，那么返回常量NoMajorityElement,该函数必须满足下面的条件：
1. 必须以O(N)时间运行。
2. 必须使用O（1）的附加空间。换句话说，可用个别的临时变量，而不可以使用任何的临时数组。并且不能使用递归解决，这是因为随着递归层数加深，会需要空间来存储栈帧。
3. 不能改变数组中的任何元素的值。
大家一起讨论下啦
………………………………………………………………………………………………………………………………………………………………………………………………
如果某个数所占比例>50%，并假设此数为M，那么：
1.如果有连续N个数都不是M，那么有有连续的M的区域累加长度必然超过M+1。
2.此情况例外：数组长度为奇数，并且数组排列为MXMXMX……MXM (X指非M的数)
[解决办法]
算法如下：
解释：只要纪录最多的和第二多的查表即可，动态规划法的一种。
#include <stdlib.h>
#include <stdio.h>
int MajorityElement(const int *p, int n){
int max=-65535,max_count=0,secend=-65535,secend_count=0,i,tmp;
for (i=0;i<n;i++){
if (max!=*(p+i)){
if (secend!=*(p+i)){
secend = *(p+i);
}
secend_count++;
if (secend_count>=max_count){
tmp = secend_count;
secend_count = max_count;
max_count = tmp;
tmp = max;
max = secend;
secend = tmp;
}
}
else
{
max_count++;
}
}
if (max_count>(n/2)){
return max;
}else
{
return -1;
}
}
int main(){
int a[10]={1,2,3,3,3,1,1,1,1,1};
printf("The Max is:=%d\n",MajorityElement(a,10));
return 0;
}