买帽子_牛客博客

（java实现）

题目描述：

度度熊想去商场买一顶帽子，商场里有N顶帽子，有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子，问第三便宜的帽子价格是多少？

输入描述：

首先输入一个正整数N（N <= 50），接下来输入N个数表示每顶帽子的价格（价格均是正整数，且小于等于1000）

输出描述：

如果存在第三便宜的帽子，请输出这个价格是多少，否则输出-1

示例1：

输入

10
10 10 10 10 20 20 30 30 40 40

输出

30

问题分析：

思路一：使用TreeSet实现；
思路二：使用ArrayList实现，但是只找倒数第三小，效率比较低。
思路三：使用下标的原理，若存在，则相应的价格设置为1；如输入的价格为price，则Array[price]=1。最后，通过求和，在求和得到“3”时进行输出。

注意：相同价格只算一个，故需要“去重”。

参考代码：

思路一实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        TreeSet<Integer> set = new TreeSet<>();
        int index;
        for (int i=0; i<n; i++)
        {
            set.add(input.nextInt());
        }
        if (set.size()<3)
        {
            System.out.println(-1);
        }
        else
        {
            System.out.println(set.toArray()[2]);
        }
    }
}

思路二实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        ArrayList<Integer> list = new ArrayList<Integer>();
        int index;
        for (int i=0; i<n; i++)
        {
            index = input.nextInt();
            if (!list.contains(index))
                list.add(index);
        }
        if (list.size()<3)
        {
            System.out.println(-1);
        }
        list.sort(Comparator.naturalOrder());
        for (int i=0; i<list.size(); i++)
        {
            if (2 == i)
            {
                System.out.println(list.get(i));
                break;
            }
        }
    }
}

思路三实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] arr = new int[1001];
        int index;
        for (int i=0; i<n; i++)
        {
            index = input.nextInt();
            arr[index] = 1;
        }
        int count = 0;
        for (int i=0; i<1001; i++)
        {
            count += arr[i];
            if (count==3)
            {
                System.out.println(i);
                break;
            }
        }
        if (count<3)
        {
            System.out.println(-1);
        }
    }
}

相关知识：
List排序函数Collections.sort
1.Java提供的默认排序算法

List<Double> list = new ArrayList();
list.add(53.6);
list.add(45.9);
list.add(75.1);
list.add(89.3);
list.add(20.8);

//升序
Collections.sort(list);
System.out.println(list.toString());
输出结果：[20.8, 45.9, 53.6, 75.1, 89.3]

List<String> list = new ArrayList();
list.add("张三");
list.add("李四");
list.add("王二");
list.add("李明");

//升序
Collections.sort(list,Collator.getInstance(java.util.Locale.CHINA));//注意：是根据的汉字的拼音的字母排序的，而不是根据汉字一般的排序方法
System.out.println(list.toString());
输出结果：[李明, 李四, 王二, 杨洋, 张三]

2.重载排序算法

//根据map里某个key的value值进行升序排序
List<LinkedTreeMap<String, Object>> companys = new ArrayList<>();
LinkedTreeMap<String, Object> map1 = new LinkedTreeMap<>();
map1.put("name", "中国");
map1.put("percent", "12%");
map1.put("span", 2.34);
companys.add(map1);

LinkedTreeMap<String, Object> map2 = new LinkedTreeMap<>();
map2.put("name", "四川");
map2.put("percent", "11%");
map2.put("span", 1.34);
companys.add(map2);

LinkedTreeMap<String, Object> map3 = new LinkedTreeMap<>();
map3.put("name", "云南");
map3.put("percent", "10%");
map3.put("span", 2.08);
companys.add(map3);

//重载排序算法
Collections.sort(companys, new Comparator<LinkedTreeMap<String, Object>>() {
    @Override
    public int compare(LinkedTreeMap<String, Object> arg0,LinkedTreeMap<String, Object> arg1) {
        Double span1 = (Double) arg0.get("span");
        Double span2 = (Double) arg1.get("span");
        return span1.compareTo(span2);
    }
}); 
System.out.println(companys.toString());

输出结果：[{name=四川, percent=11%, span=1.34}, {name=云南, percent=10%, span=2.08}, {name=中国, percent=12%, span=2.34}]