2731. 移动机器人 (opens new window)

1.排序+找规律

本题直接暴力模拟会超时，因此需要另外找规律降低时间复杂度。

• 题目最终需要计算机器人两两之间的距离，那么对应改变机器人的标号不会影响计算结果，只需要保证距离是正确的即可。
• 考虑碰撞处理主要分为两种情况：
  • 当前这一秒移动后，a和b落脚在同一个坐标上inx，并改变移动方向。实际上下一秒inx+1坐标上是a还是b对最终结果不会产生影响，也就是说我们可以当作"方向没有改变"来处理。
  • 当前a和b分别位于inx和inx+1，那么下一秒移动后如果当作”方向未改变“来处理，那么就会a位于inx+1，b位于inx，和当前坐标状态相比也不会影响最终结果。

因此机器人移动时不需要处理碰撞，直接按照初始方向移动即可。问题简化为计算两两距离之和，常规做法两个for循环时间O(n平方)，另一种做法是从小到大排序，观察可以发现第一个数字被减了n-1次，第二个数字被减n-2次，同时加了1次，第三个数字被减了n-3次，同时加了2次...以此类推可以只用一个循环计算，时间O(n)

class Solution {
    public int sumDistance(int[] nums, String s, int d) {
        long[] arr=new long[nums.length];
        long sum=0;
        for(int i=0;i<nums.length;i++){
            if(s.charAt(i)=='R') arr[i]=nums[i]+d;
            else arr[i]=nums[i]-d;
            sum+=arr[i];
        }
        Arrays.sort(arr);
        int n=nums.length;
        long res=0;
        for(int i=0;i<nums.length;i++){
            n--;
            sum-=arr[i];
            res=(res+sum-n*arr[i])%1000000007;
        }
        return (int)res;
    }
}