时间戳

首页 > 解决方案 > 里程碑问题中的最低最大访问次数

arrays - 里程碑问题中的最低最大访问次数

问题描述

嗨，我遇到了一个问题，我得到了 1、50000、10000、3、10001、10003 之类的数字，并假设它们是跑步者跨越的里程碑。

所以这意味着，首先他会从 1 跑到 50k，然后回到 10k，然后跑到 3，然后跑到 10001 和 10003 等等。现在我必须找到他整个旅程中最低的最大访问里程碑。

这是我写的程序。有没有更好的版本，使用更少的空间而不是 50k 数组。

public class LowestMaxVisits {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(50000);
        list.add(10000);
        list.add(3);
        list.add(10001);
        list.add(10003);
        int [] arr = new int[50000];
        long smillis = System.currentTimeMillis() % 1000;
        for(int i=0; i<list.size()-1; i++){
            int start = list.get(i)-1;
            int end = list.get(i+1)-1;
            if(start > end){
                int temp = start;
                start = end;
                end = temp;
            }
            while(start < end){
                arr[start]++;
                arr[end]++;
                start++;
                end--;
            }
        }
        int maxVisits = -1;
        int index = -1;
        for(int k=0;k<arr.length;k++){
            if(arr[k] > maxVisits){
                index = k;
                maxVisits = arr[k];
            }
        }
        long emillis = System.currentTimeMillis() % 1000;
        System.out.println("Time taken---"+ (emillis-smillis));
        System.out.println("Here is the highest---"+(index+1));
    }
}

标签： arraysalgorithm

解决方案

这是基于我在评论中解释解决问题的方式的代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class LowestMaxVisits {

    public static void main(String[] args) {
        List<Integer> milestones = new ArrayList<Integer>(){{
            add(1);
            add(50000);
            add(10000);
            add(3);
            add(10001);
            add(10003);
        }};

        System.out.println(getHighestMilestone(milestones));
    }

    public static int getHighestMilestone(List<Integer> milestones) {
        // Make a sorted milestones array
        List<Integer> sortedMilestones = new ArrayList<>(milestones);
        int t;
        for (int i = 0; i < sortedMilestones.size() - 1; i++) {
            for (int j = sortedMilestones.size() - 1; j > i; j--) {
                if (sortedMilestones.get(i) > sortedMilestones.get(j)) {
                    t = sortedMilestones.get(i);
                    sortedMilestones.set(i, sortedMilestones.get(j));
                    sortedMilestones.set(j, t);
                }
            }
        }
        // Count the amount of times passed for each milestone
        t = 0;
        int[] mPassed = new int[sortedMilestones.size()];
        for (int i = 0; i < milestones.size() - 1; i++) {
            if (i == 0 || (milestones.get(i) > sortedMilestones.get(t))) {
                for (int j = t + 1; j < sortedMilestones.size(); j++) {
                    mPassed[j]++;
                    if (Objects.equals(sortedMilestones.get(j), milestones.get(i))) {
                        t = j;
                        break;
                    }
                }
            } else {
                for (int j = t - 1; j >= 0; j--) {
                    mPassed[j]++;
                    if (Objects.equals(sortedMilestones.get(j), milestones.get(i))) {
                        t = j;
                        break;
                    }
                }
            }
        }
        // Get the highest count and set it to t
        t = 0;
        for (int i = 0; i < mPassed.length; i++) {
            if (t < mPassed[i]) {
                t = mPassed[i];
            }
        }
        // Get lowest milestone with the higest count
        for (int i = 0; i < mPassed.length; i++) {
            if (mPassed[i] == t) {
                t = sortedMilestones.get(i);
                break;
            }
        }
        return t;
    }

}

您需要对复制的数组进行排序，以便按照停靠点的顺序来回遍历它们，就像它们是“地方”一样。您还需要它来查找访问次数最多的最少里程碑。

编辑：而不是制作一个与我们数组中的最大数字（在您的情况下为 50,000）一样大的列表，这只需要制作里程碑数组和另一个相同大小的整数数组的副本。注意：int t;在整个getHighestMilestone().

推荐阅读