map练习

以你之姓@ 2023-07-10 14:17 20阅读 0赞

**小明最近在研究压缩算法。**  
他知道，压缩的时候如果能够使得数值很小，就能通过熵编码得到较高的压缩比。然而，要使数值很小是一个挑战。最近，小明需要压缩一些正整数的序列，这些序列的特点是，后面出现的数字很大可能是刚出现过不久的数字。对于这种特殊的序列，小明准备对序列做一个变换来减小数字的值。变换的过程如下：从左到右枚举序列，每枚举到一个数字，如果这个数字没有出现过，将数字变换成它的相反数，如果数字出现过，则看它之前在原序列中最后的一次出现后面（且在当前数前面）出现了几种数字，用这个种类数替换原来的数字。比如，序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在变换过程为：

a1: 1未出现过，所以a1变为-1；
    a2: 2未出现过，所以a2变为-2；
    a3: 2出现过，最后一次为原序列的a2，在a2后、a3前有0种数字，所以a3变为0；
    a4: 1出现过，最后一次为原序列的a1，在a1后、a4前有1种数字，所以a4变为1；
    a5: 2出现过，最后一次为原序列的a3，在a3后、a5前有1种数字，所以a5变为1。

现在，给出原序列，请问，按这种变换规则变换后的序列是什么。  
**输入格式**：  
输入第一行包含一个整数n，表示序列的长度。  
第二行包含n个正整数，表示输入序列。  
**输出格式：**  
输出一行，包含n个数，表示变换后的序列。  
**例如，输入**：

5
    1 2 2 1 2

**程序应该输出：**

-1 -2 0 1 1

**再例如，输入**：

12
    1 1 2 3 2 3 1 2 2 2 3 1

**程序应该输出：**

-1 0 -2 -3 1 1 2 2 0 0 2 2

**数据规模与约定**  
对于30%的数据，n<=1000；  
对于50%的数据，n<=30000；  
对于100%的数据，1 <=n<=100000，1<=ai<=10^9

**基本思路**  
主要是创建一个0/1数组flag,用来存每种数字的最后一次出现的下标位置，1表示新的种类数字最后一次出现的位置，然后创建hashmap存放每一种数字最后一次出现的 <值-最后出现的下标> 映射，这样通过值可以直接get到最后的下标，然后每输入一个数即开始判断输出一个结果到存结果的数组中。

## 详细代码 ##

import java.lang.reflect.Array;
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
     
    public class 压缩变换_10 {
        
    	static int flag[],ans[];//flag/0/1/数组存最后一次出现的数字种类的下标，ans数组存答案
    	static Map<Integer,Integer> map = new HashMap<Integer,Integer>(); //存放之前没出现过的数的下标，值
    	public static int count(int l,int r)//返回l,r之间（不包括r）的数字种类
    	{
        
    		int sum = 0;
    		for(int i =l;i<r;i++)
    		{
        
    			if(flag[i]==1)
    				sum++;
    		}
    		return sum;
    	}
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int num,n;
    		Scanner in = new Scanner(System.in);
    		num = in.nextInt();
    		flag = new int[num];
    		ans = new int[num];
    		Arrays.fill(flag,0);//把flag数组全部填充0;
    		
    		for(int i=0;i<num;i++)
    		{
        
    			n = in.nextInt();
    			if(!map.containsKey(n))//map中不包括数n
    			{
        
    				ans[i]=-n;
    				map.put(n, i);//把下标i存为值，数n存为键，这样保证键的唯一性，即存进去的数n是唯一的
    				flag[i] = 1;
    			}
    			else//map中之前出现过数n
    			{
        
    				int lastIndex = map.get(n);//获得n上一次出现的下标，这里证明了存放时n应该是键，取出来的值是下标i,如果顺序反过来，hashmap不能通过值获得唯一键，只能通过键获得一个值
    				flag[lastIndex]=0;
    				int numType = count(lastIndex+1,i);
    				ans[i] = numType;
    				map.put(n, i);
    				flag[i]=1;
    			}
    		}
    		for(int i = 0;i<ans.length;i++)
    		{
        
    			System.out.print(ans[i]+" ");
    		}
    		
    	}
     
    }