HackerLand National Bank 有一個簡單的政策來警告客戶可能的欺詐賬戶活動。如果客戶在某一天花費的金額大于或等于客戶連續幾天的中位數花費，他們會向客戶發送有關潛在欺詐的通知。銀行不會向客戶發送任何通知，直到他們至少擁有前幾天交易數據的尾隨數量。我寫了下面的代碼。但是，該代碼適用于某些測試用例，并且某些測試用例會“因超時而終止”。誰能告訴我如何改進代碼？import java.io.*;import java.math.*;import java.security.*;import java.text.*;import java.util.*;import java.util.concurrent.*;import java.util.regex.*;public class Solution { // Complete the activityNotifications function below. static int activityNotifications(int[] expenditure, int d) { /Delaring Variables int iterations,itr,length,median,midDummy,midL,midR, midDummy2,i,i1,temp,count; float mid,p,q; length = expenditure.length; iterations = length-d; i=0; i1=0; itr=0; count = 0; int[] exSub = new int[d]; while(iterations>0) { // Enter the elements in the subarray while(i1<d) { exSub[i1]=expenditure[i+i1]; //System.out.println(exSub[i1]); i1++; } //Sort the exSub array for(int k=0; k<(d-1); k++) { for(int j=k+1; j<d; j++) { if(exSub[j]<exSub[k]) { temp = exSub[j]; exSub[j] = exSub[k]; exSub[k] = temp; } } } //Printing the exSub array in each iteration for(int l = 0 ; l<d ; l++) { System.out.println(exSub[l]); } i1=0; }}
2 回答
犯罪嫌疑人X
TA貢獻2080條經驗 獲得超4個贊
性能改進的第一條規則是：如果不需要，不要改進性能。
性能改進通常會導致代碼可讀性降低，因此只有在真正需要時才應該這樣做。
第二條規則是：在低級改進之前改進算法和數據結構。
如果您需要提高代碼的性能，請在進行低級改進之前始終嘗試使用更高效的算法和數據結構。在您的代碼示例中是：不要使用BubbleSort，但嘗試使用更高效的算法，如Quicksort或Mergesort，因為它們使用時間復雜度，O(n*log(n)而 Bubble sort 的時間復雜度O(n^2)在您必須進行大排序時要慢得多陣列。您可以使用Arrays.sort(int[])來執行此操作。
您的數據結構只是數組，因此無法在您的代碼中進行改進。
這將為您的代碼提供相當大的加速，并且不會導致無法再讀取代碼。諸如使用移位和其他快速計算（如果經常使用則很難理解）將簡單計算更改為稍微更快的計算等改進幾乎總是會導致代碼只是稍微快一點，但沒有人能夠再輕松理解它.
可以應用于您的代碼的一些改進（也只會略微提高性能）是：
while如果可能，用循環替換for循環（它們可以由編譯器改進）System.out.println如果不是完全需要，請不要用于許多文本（因為它對于大文本來說很慢）嘗試使用System.arraycopy復制數組，這通常比使用 while 循環復制更快
因此，您的改進代碼可能如下所示（我用注釋標記了更改的部分）：
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
// Complete the activityNotifications function below.
static int activityNotifications(int[] expenditure, int d) {
//Delaring Variables
int iterations, itr, length, median, midDummy, midL, midR, midDummy2, i, i1, temp, count;
float mid, p, q;
length = expenditure.length;
iterations = length - d;
i = 0;
i1 = 0;
itr = 0;
count = 0;
int[] exSub = new int[d];
//EDIT: replace while loops with for loops if possible
//while (iterations > 0) {
for (int iter = 0; iter < iterations; iter++) {
//EDIT: here you can again use a for loop or just use System.arraycopy which should be (slightly) fasters
// Enter the elements in the subarray
/*while (i1 < d) {
exSub[i1] = expenditure[i + i1];
//System.out.println(exSub[i1]);
i1++;
}*/
System.arraycopy(expenditure, i, exSub, 0, d);
//EDIT: Don't use bubble sort!!! It's one of the worst sorting algorithms, because it's really slow
//Bubble sort uses time complexity O(n^2); others (like merge-sort or quick-sort) only use O(n*log(n))
//The easiest and fastest solution is: don't implement sorting by yourself, but use Arrays.sort(int[]) from the java API
//Sort the exSub array
/*for (int k = 0; k < (d - 1); k++) {
for (int j = k + 1; j < d; j++) {
if (exSub[j] < exSub[k]) {
temp = exSub[j];
exSub[j] = exSub[k];
exSub[k] = temp;
}
}
}*/
Arrays.sort(exSub);
//Printing the exSub array in each iteration
//EDIT: printing many results also takes much time, so only print the results if it's really needed
/*for (int l = 0; l < d; l++) {
System.out.println(exSub[l]);
}*/
i1 = 0;
//For each iteration claculate the median
if (d % 2 == 0) // even
{
midDummy = d / 2;
p = (float) exSub[midDummy];
q = (float) exSub[midDummy - 1];
mid = (p + q) / 2;
//mid = (exSub[midDummy]+exSub [midDummy-1])/2;
//System.out.println(midDummy);
}
else // odd
{
midDummy2 = d / 2;
mid = exSub[midDummy2];
//System.out.println(midDummy2);
}
if (expenditure[itr + d] >= 2 * mid) {
count++;
}
itr++;
i++;
//iterations--;//EDIT: don't change iterations anymore because of the for loop
System.out.println("Mid:" + mid);
System.out.println("---------");
}
System.out.println("Count:" + count);
return count;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nd = scanner.nextLine().split(" ");
int n = Integer.parseInt(nd[0]);
int d = Integer.parseInt(nd[1]);
int[] expenditure = new int[n];
String[] expenditureItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < n; i++) {
int expenditureItem = Integer.parseInt(expenditureItems[i]);
expenditure[i] = expenditureItem;
}
int result = activityNotifications(expenditure, d);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
編輯：
如果您不在每次迭代中對完整（子）數組進行排序，而是僅刪除一個值（不再使用的第一天）并添加一個新值（不再使用的新日期），則可以使解決方案更快現在使用）在正確的位置（就像@Vojtěch Kaiser 在他的回答中提到的那樣）
這將使它更快，因為對數組進行排序需要時間，而將新值添加到數組中時，如果您使用搜索樹，O(d*log(d))則已經排序的新值只需要時間。O(log(d))使用數組時（就像我在下面的示例中所做的那樣）需要時間O(d)，因為使用數組時您需要復制需要線性時間的數組值（如評論中提到的@dyukha）。因此（再次）可以通過使用更好的算法來進行改進（也可以通過使用搜索樹而不是數組來改進此解決方案）。
所以新的解決方案可能是這樣的：
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
// Complete the activityNotifications function below.
static int activityNotifications(int[] expenditure, int d) {
//Delaring Variables
int iterations, length, midDummy, midDummy2, count;//EDIT: removed some unused variables here
float mid, p, q;
length = expenditure.length;
iterations = length - d;
count = 0;
//EDIT: add the first d values to the sub-array and sort it (only once)
int[] exSub = new int[d];
System.arraycopy(expenditure, 0, exSub, 0, d);
Arrays.sort(exSub);
for (int iter = 0; iter < iterations; iter++) {
//EDIT: don't sort the complete array in every iteration
//instead remove the one value (the first day that is not used anymore) and add the new value (of the new day) into the sorted array
//sorting is done in O(n * log(n)); deleting and inserting a new value into a sorted array is done in O(log(n))
if (iter > 0) {//not for the first iteration
int remove = expenditure[iter - 1];
int indexToRemove = find(exSub, remove);
//remove the index and move the following values one index to the left
exSub[indexToRemove] = 0;//not needed; just to make it more clear what's happening
System.arraycopy(exSub, indexToRemove + 1, exSub, indexToRemove, exSub.length - indexToRemove - 1);
exSub[d - 1] = 0;//not needed again; just to make it more clear what's happening
int newValue = expenditure[iter + d - 1];
//insert the new value to the correct position
insertIntoSortedArray(exSub, newValue);
}
//For each iteration claculate the median
if (d % 2 == 0) // even
{
midDummy = d / 2;
p = exSub[midDummy];
q = exSub[midDummy - 1];
mid = (p + q) / 2;
//mid = (exSub[midDummy]+exSub [midDummy-1])/2;
//System.out.println(midDummy);
}
else // odd
{
midDummy2 = d / 2;
mid = exSub[midDummy2];
//System.out.println(midDummy2);
}
if (expenditure[iter + d] >= 2 * mid) {
count++;
}
}
System.out.println("Count:" + count);
return count;
}
/**
* Find the position of value in expenditure
*/
private static int find(int[] array, int value) {
int index = -1;
for (int i = 0; i < array.length; i++) {
if (array[i] == value) {
index = i;
}
}
return index;
}
/**
* Find the correct position to insert value into the array by bisection search
*/
private static void insertIntoSortedArray(int[] array, int value) {
int[] indexRange = new int[] {0, array.length - 1};
while (indexRange[1] - indexRange[0] > 0) {
int mid = indexRange[0] + (indexRange[1] - indexRange[0]) / 2;
if (value > array[mid]) {
if (mid == indexRange[0]) {
indexRange[0] = mid + 1;
}
else {
indexRange[0] = mid;
}
}
else {
if (mid == indexRange[1]) {
indexRange[1] = mid - 1;
}
else {
indexRange[1] = mid;
}
}
}
System.arraycopy(array, indexRange[0], array, indexRange[0] + 1, array.length - indexRange[0] - 1);
array[indexRange[0]] = value;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nd = scanner.nextLine().split(" ");
int n = Integer.parseInt(nd[0]);
int d = Integer.parseInt(nd[1]);
int[] expenditure = new int[n];
String[] expenditureItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < n; i++) {
int expenditureItem = Integer.parseInt(expenditureItems[i]);
expenditure[i] = expenditureItem;
}
int result = activityNotifications(expenditure, d);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
//Just for testing; can be deleted if you don't need it
/*int[] exp = new int[] {2, 3, 4, 2, 3, 6, 8, 4, 5};
int d = 5;
activityNotifications(exp, d);
int[] exp2 = new int[] {1, 2, 3, 4, 4};
d = 4;
activityNotifications(exp2, d);*/
}
}
白板的微信
TA貢獻1883條經驗 獲得超3個贊
您主要擔心的是您在每次迭代中都對部分數組進行排序，從而使問題的總復雜度增加O(nd log(d)) ，對于大的d值，這可能會變得非常棘手。
您想要的是在迭代之間對數組進行排序并對更改的值進行排序/排序。為此，您將實施二叉搜索樹（BST）或其他一些平衡選項（AVL，...），執行O(log(d))刪除最舊的值，然后執行O(log(d))插入新值, 并簡單地在中間尋找中位數?？偟臐u近復雜度為O(n log(d))，據我所知這是你能得到的最好的——其余的優化是低級的臟工作。
看看 java https://docs.oracle.com/javase/10/docs/api/java/util/TreeSet.html，它應該處理大部分工作，但請記住底層結構是由比數組慢的對象組成。
添加回答
舉報
0/150
提交
取消