求指定规则数列的第N项

题目描述

给定两个正整数 M 和 N，求满足下列规则的数列的第 N 项。

1. 数列的前 M 项是 1 到 M。
2. 数列从第 M + 1 项开始，如果前 M 项中存在相同的数，则第 M + 1 项等于前 M 项最大值和最小值的和，如果前 M 项中不存在相同的数，则第 M + 1 项等于前 M 项中最小值和最小值的差。

示例：
输入：5, 1
输出：1
解释：前 5 项为 [1, 2, 3, 4, 5]，第 1 项为 1。

输入：5, 6
输出：4
解释：前 6 项为 [1, 2, 3, 4, 5, 4]，第 1 项为 1。

思路

先写出前 M 项，并扔到一个 Set 中，并且动态记录前 M 项的最大值和最小值。求第 M + 1 项的时候看 Set 的长度是否等于 M，如果不等于，说明有重复值，求和，否则求差。然后清空 Set，重置最大值最小值，求下一项。

代码实现

public static int calculateSequence(int M, int N) {  
    List<Integer> list = new LinkedList<>();  
    for (int i = 1; i <= M; i++) {  
        list.add(i);  
    }  
    if (N <= M) {  
        return list.get(N - 1);  
    }  
    int t = M;  
    int tempMax = M;  
    int tempMin = 1;  
    while (t < N) {  
        Set<Integer> set = new LinkedHashSet<>(list);  
        int tempVal = 0;  
        if (set.size() == list.size()) {  
            tempVal = tempMax - tempMin;  
        } else {  
            tempVal = tempMax + tempMin;  
        }  
        list.remove(0);  
        list.add(tempVal);  
  
        tempMax = max(list);  
        tempMin = min(list);  
  
        t++;  
    }  
    return list.get(list.size() - 1);  
}  
  
private static int max(List<Integer> list) {  
    int maxVal = Integer.MIN_VALUE;  
    for (Integer i : list) {  
        maxVal = Math.max(maxVal, i);  
    }    return maxVal;  
}  
  
private static int min(List<Integer> list) {  
    int minVal = Integer.MAX_VALUE;  
    for (Integer i : list) {  
        minVal = Math.min(minVal, i);  
    }    return minVal;  
}