[数据结构与算法]ACWing3761 唯一最小树

题目

输入样例
6
2
1 1
3
2 1 3
4
2 2 2 3
1
1
5
2 3 2 4 2
6
1 1 5 5 4 4
输出样例
-1
2
4
1
2
-1

题解

这道题如果按正常的思路去做的话会超时，所以要优化算法
我们使用m来存下标、w[m]来存数值、cnt[w[m]]来存这个数出现了几次，ans来存答案，经过判断即可得到最终结果，值得一提的是一开始我使用java中的Arrays.fill()方法来清空数组，最后仍然会超时，所以后面我手动清空数组，减少了时间复杂度

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int w[] = new int[200500];
        int cnt[] = new int[200500];
        Scanner scanner = new Scanner(System.in);
        int n,m;
        n=scanner.nextInt();
        for(int i = 0 ;i < n; i++){
            m=scanner.nextInt();
			//存数据
            for(int j = 1;j <= m ; j++){
                w[j]=scanner.nextInt();
                cnt[w[j]]++;
            }
            int ans=-1;
            for(int j = 1; j <= m ; j++){
            	//核心判断语句
                if(cnt[w[j]]!=1)continue;
                if(ans==-1||w[j]<w[ans]){
                    ans=j;
                }
            }
            System.out.println(ans);
            //清空使用过的数组
            for(int j = 1; j <= m ; j++){
                cnt[w[j]]=0;
            }
        }
    }
}