Sorting - Fraudulent Activity Notifications [M]

Key: 中位數, 所有數字由低到高排序後,取中間的數 

For example,  and . On the first three days, they just collect spending data. At day , we have trailing expenditures of . The median is  and the day's expenditure is . Because , there will be a notice. The next day, our trailing expenditures are  and the expenditures are . This is less than  so no notice will be sent. Over the period, there was one notice sent.

Sample Input 0

9 5

2 3 4 2 3 6 8 4 5

Sample Output 0

2

static int activityNotifications(int[] expenditure, int d) {

      int notificationCount = 0;

        int[] data = new int[201];

        for (int i = 0; i < d; i++) {

            data[expenditure[i]]++;

        }

        for (int i = d; i < expenditure.length; i++) {

            double median = getMedian(d, data);

            if (expenditure[i] >= 2 * median) {

                notificationCount++;

            }

            data[expenditure[i]]++;

            data[expenditure[i - d]]--;

        }

        return notificationCount;

    }

    private static double getMedian(int d, int[] data) {

        double median = 0;

        if (d % 2 == 0) {

            Integer m1 = null;

            Integer m2 = null;

            int count = 0;

            for (int j = 0; j < data.length; j++) {

                count += data[j];

                if (m1 == null && count >= d/2) {

                    m1 = j;

                }

                if (m2 == null && count >= d/2 + 1) {

                    m2 = j;

                    break;

                }

            }

            median = (m1 + m2) / 2.0;

        } else {

            int count = 0;

            for (int j = 0; j < data.length; j++) {

                count += data[j];

                if (count > d/2) {

                    median = j;

                    break;

                }

            }

        }

        return median;

    }