当前页面: 开发资料首页 → J2SE 专题 → 一个有挑战性的算法题!!!

一个有挑战性的算法题!!!

摘要: 一个有挑战性的算法题!!!

数组T[n]，找出他的主元素，要求时间复杂度为O(n);
主元素：在T[n]中重复个数迢过n/2的数

---

找第n/2 和n-n/2大的数，然后检查这两个哪个是

---

mark

---

期待

---

找第n/2 和n-n/2大的数，然后检查这两个哪个是
这个算法，很明显的不对，举个反例：
2 3 4 5 6 6 6 6 6
按题意结果应该是6
而按这个算法则是在2和3选一个

---

int t[]={14,4,22,3,4,5,5,4,5,4,5,4,5,4,4};

Arrays.sort(t);

System.out.println(t[t.length/2]);

---

sort(t);不用复杂度的吗？这样当然不行了

---

都不对，想想

---

设T[0:n-1]是n个元素的数组。对任意一个元素x，设S(x)={i|T[i]=x}。当|S(x)|〉n/2时，称x为T的主元素。设计一个线性时间算法，确定T[0:n-1]是否有一个主元素。
b) 分析
通过对问题目的性的研究，可以得到这样的一个结论：
在元素数组中，删去不同的两个元素，数组的主元素保持不变。
按照这样的思路，我们可以不断缩小问题的规模，最终使问题得解：
设置变量Seed用于存储当前候选元素，初始化为数组首元素a[0]；
设置变量count用于控制候选元素，初始化为1；
从第二个元素a[1]开始遍历数组，并与Seed相比较：
相同，则count加1，读入下一个元素；
不同，则count减1，读入下一个元素：相当于删去两个不同元素，缩小问题规模；
如果count小于0则Seed不是主元素候选，读入下一个元素，count加1。
这样一次遍历之后，得到的Seed就是主元素的候选；
但因为最终得到的Seed元素有可能是序列最末位的两个元素之一，所以还需要验证。
我们再次遍历数组，得到Seed出现的次数，与总数的一半比较来验证。

---

/**判断输入的数列是否有主元素
*/
private static boolean hasMaster(int data[], int n)
{
int count=0; //保存计数
int seed; //保存参照元素

seed = data[0];

for(int i=1; i {
if(seed == data[i]) //如果数据相同，计数加一
{
count++;
}
if(seed == data[i])
{
if(count>0)

{
count--; //如果数据不同，则计数减一
//相当于删除两个不同的元素
//不会对主元素造成影响
}
else
{
seed = data[i]; //计数为零时，seed不可能为主元素
//读入新数据
}
} //end of if
} //end of for

//因为最终得到的seed元素有可能是序列最末位的两个元素之一
//因此，这里还需要验证
count = 0;
for(int i=0; i {
if (seed == data[i])
count++;
}

if(count>(n/2))
{
return true;
}

return false;

}
}

---

在元素数组中，删去不同的两个元素，数组的主元素保持不变
一语中地！！！！！！

---