I have developed the below logic but it fails to execute in the given time. Its taking more than 4 seconds for a test data set of 100k numbers. Can someone suggest or optimize it to run within 0.2 seconds for a large data set. The problem statement is as below:
A radio center receives some signals and needs to classify them according to frequency.
There are standard frequencies known to the center. They have identified
different signals which are to be classified. Given the standard signal frequencies freq_standard and frequencies of signals to be classified freq_signal, can you help the radio center identify them?
A signal X belongs to a standard signal Y if the frequency of X is closer to that of Y than to any other frequency. If it is equidistant from two known frequencies, then the signal with higher frequency is chosen.
Consider, for example, freq_standard = [2, 3, 1, 4, 8] and freq_classify = [1, 5, 6]. Frequencies 1 and 5 belong to standard frequencies 1(index=3) and 4(index=4) respectively. Since 6 is equidistant from two standard frequencies, 4 and 8, choose the higher frequency, 8(index=5). The corresponding classifications are [3, 4, 5].
Function Description:
Complete the function classifySignals in the editor below. The function must return an integer array denoting the classifications of each frequency.
classifySignals has two parameters -
freq_standard: an integer array
freq_signals: an integer array
Input Format:
The first line of input contains 2 space-separated integers: n,q- the number of strings and the number of queries.
The second line contains space-separated integers, the array freq_standard.
The next line contains q space-separated integers, the array freq_signals.
Constraints:
n <= 105
q <= 105
|freq_standardi| <= 109
|freq_signalsi| <= 109
Output Format:
Print q lines: each line should contain an integer representing the index of the standard frequency corresponding to the given signal. There is a code stub to handle I/O if you choose to use it.
Sample Input 0:
5 5
7 1 12 9 15
2 9 2000 13 4
Sample Output 0:
2
4
5
3
1
My attempt:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Result1 {
/*
* Complete the 'classifySignals' function below.
*
* The function is expected to return an INTEGER_ARRAY. The function accepts
* following parameters: 1. INTEGER_ARRAY freq_standard 2. INTEGER_ARRAY
* freq_signals
*/
public static List<Integer> classifySignals(List<Integer> freq_standard, List<Integer> freq_signals) {
List<Integer> out = new ArrayList<>();
int match = 0;
int n = freq_standard.size();
int q = freq_signals.size();
List<Integer> freq_standard_unordered = new ArrayList<>(freq_standard);
Collections.sort(freq_standard);
for (int i = 0; i < q; i++) {
int signalToCompare = freq_signals.get(i);
if (signalToCompare < freq_standard.get(0)) {
match = freq_standard.get(0);
out.add(freq_standard_unordered.indexOf(match) + 1);
continue;
}
if (signalToCompare > freq_standard.get(n - 1)) {
match = freq_standard.get(n - 1);
out.add(freq_standard_unordered.indexOf(match) + 1);
continue;
}
int j = 0, k = n, mid = 0;
while (j < k) {
mid = (j + k) / 2;
if (freq_standard.get(mid) == signalToCompare) {
match = freq_standard.get(mid);
break;
}
if (signalToCompare < freq_standard.get(mid)) {
match = mid - 1 > 0
? findClosest(freq_standard.get(mid), freq_standard.get(mid - 1), signalToCompare)
: freq_standard.get(mid);
k = mid;
} else {
match = mid + 1 < n
? findClosest(freq_standard.get(mid + 1), freq_standard.get(mid), signalToCompare)
: freq_standard.get(mid);
j = mid + 1;
}
}
out.add(freq_standard_unordered.indexOf(match) + 1);
}
return out;
}
public static int findClosest(int n, int m, int target) {
if (Math.abs(n - target) == Math.abs(m - target)) {
return n;
}
if (Math.abs(n - target) > Math.abs(m - target)) {
return m;
} else {
return n;
}
}
}
public class GFG {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int q = Integer.parseInt(firstMultipleInput[1]);
String[] fTemp = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
List<Integer> f = new ArrayList<>();
for (int i = 0; i < n; i++) {
int fItem = Integer.parseInt(fTemp[i]);
f.add(fItem);
}
String[] FTemp = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
List<Integer> F = new ArrayList<>();
for (int i = 0; i < q; i++) {
int FItem = Integer.parseInt(FTemp[i]);
F.add(FItem);
}
List<Integer> ans = Result1.classifySignals(f, F);
System.out.println(ans);
}
}
You have
out.add(freq_standard_unordered.indexOf(match) + 1);
Which is finding the index of the match that takes O(n) in the worst case in itself. This is also inside a loop which makes it O(n2).
Your idea of binary search is correct. But, while sorting, you can't lose indices of elements, which is what actually made you do out.add(freq_standard_unordered.indexOf(match) + 1);
To avoid this, you can make a class(or have a 2D array) which stores value as well as index and do binary search on them accordingly. This way, you can correctly judge actual index of an element in it's original ordering. Below is how I did it(note that it can have some unnecessary checks, but you get the idea of the overall strategy anyway)
Snippet:
class Result {
static class Data{
int val,actual_index;
Data(int val,int index){
this.val = val;
this.actual_index = index;
}
}
public static List<Integer> classifySignals(List<Integer> freq_standard, List<Integer> freq_signals) {
Data[] d = new Data[freq_standard.size()];
for(int i=0;i<d.length;++i) d[i] = new Data(freq_standard.get(i),i);
Arrays.sort(d,new Comparator<Data>(){
public int compare(Data d1,Data d2){
if(d1.val <= d2.val) return -1;
return 1; // not doing d1.val - d2.val to avoid overflows(although irrelevant here)
}
});
int size = freq_signals.size();
List<Integer> ans = new ArrayList<>();
for(int i = 0;i < size; ++i){
int ele = freq_signals.get(i);
int index = getClosest(d,freq_standard,ele);
ans.add(index + 1);
}
return ans;
}
private static int getClosest(Data[] d,List<Integer> freq_standard,int ele){
int index = -1;
int low = 0,high = d.length - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(d[mid].val == ele) return d[mid].actual_index;
if(d[mid].val > ele){
if(index == -1 || Math.abs(freq_standard.get(d[index].actual_index) - ele) > Math.abs(d[mid].val - ele)) index = mid;
high = mid - 1;
}else{
if(index == -1 || Math.abs(freq_standard.get(d[index].actual_index) - ele) > Math.abs(d[mid].val - ele)) index = mid;
low = mid + 1;
}
}
if(index + 1 < d.length){
int current_closest = freq_standard.get(d[index].actual_index);
int next_closest = freq_standard.get(d[index + 1].actual_index);
if(Math.abs(ele - current_closest) == Math.abs(ele - next_closest)) return d[index + 1].actual_index;
}
return d[index].actual_index;
}
}