首页 > 代码库 > 软件工程个人作业05
软件工程个人作业05
寻找水王
这次的题目有点意思,不过也很有挑战。最难的就是时间复杂度度必须是O(n),也就是说只能遍历一次。最开始我的想法是,若要节约时间,那么就只能那空间去补了。为每个ID建立一个空间用来存放当下ID的发帖数,这样就至少要消耗额外的n个空间了。后来在老师的提醒小终于有了更好的方法。思路如下:
因为题目规定水王发帖的数目超过了所有帖子的一半,所以可以可以在遍历数组的时候,将不相同的两个元素都进行标记,最后就只剩下水王的帖子没有标记完。
程序代码如下:
public class FindWaterKing { public static void main(String[] args) { // TODO Auto-generated method stub int a[] = {1,2,1,2,2,1,1,3,1,2,1,4,1}; int len = a.length; for(int i = 0; i < len ; i++) { System.out.printf("%d ",a[i]); } System.out.println("水王是:"+getKing(a)); } /** * @param array 表示存放帖子的数组,数组的元素为用户的ID * @return 水王的ID */ public static int getKing(int[] array) { int len = array.length; // 帖子的数量 int result = 0; // 开始默认水王为下标为0的ID for(int i = 1; i < len; i++) // 遍历所有帖子 { if(array[result]==array[i]); // 如果水王的的ID和当前ID相同,什么也不做 else // 如果不相同,则需要将当前ID和水王ID抵消 { int temp = array[result]; // 记录下水王的ID boolean flag = true; // 记录从水王的下标到当前下标i之间是否还有水王的帖子,默认为true while(result<=i&&flag){ // 水王的下标向后移动,查找是否还有水王 result++; if(array[result]==temp) // 如果当前下标i之前会有一个水王的帖子,循环结束。 flag = false; } } } return array[result]; } }
实验截图:
个人总结:遇到问题对总结分析,仔细的考虑,有时候要从多角度去分析,也许换个思路就能就决问题。从自然世界到抽象世界的转换自然有着一定的难度,这需要一定的思维逻辑能力,所以平时可以多看看这样的书。
软件工程个人作业05
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。