首页 > 代码库 > 软件工程个人作业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