`

Leetcode - Largest Number

 
阅读更多
Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

[分析] 贪心思想,任两个数字字符串a, b, 若 a + b > b + a, 则a 应排在 b 前面。
注意点:
1.Arrays.sort()不支持给int数组传自定义比较器,因此需要转为String数组进行排序。
2.要判断并处理前缀为0的结果。


public class Solution {
    Comparator<String> comparator = new Comparator<String>() {
        public int compare(String a, String b) {
            String result1 = a + b;
            String result2 = b + a;
            return result1.compareTo(result2);
        }  
    };
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0)
            return "";
        int N = nums.length;
        String[] numstrs = new String[N];
        for (int i = 0; i < N; i++)
            numstrs[i] = String.valueOf(nums[i]);
        Arrays.sort(numstrs, comparator);
        StringBuilder sb = new StringBuilder();
        for (int i = N - 1; i >= 0; i--)
            sb.append(numstrs[i]);
        
        // truncate prefix 0 
        // style 1
/*        if (sb.charAt(0) == '0' && N > 1) {
            int j = 0;
            while (j < sb.length() - 1 && sb.charAt(j) == '0')
                j++;
            sb.delete(0, j);
        }
        return sb.toString();*/
        // style 2
        int i = 0;
        while (i < sb.length() && sb.charAt(i) == '0')
            i++;
        if (i == sb.length()) 
            return "0";
        else 
            return sb.substring(i, sb.length());
    }
}
分享到:
评论

相关推荐

    java-leetcode题解之179-Largest-Number

    java入门 java_leetcode题解之179_Largest_Number

    python-leetcode题解之179-Largest-Number.py

    python python_leetcode题解之179_Largest_Number.py

    算法-leetcode-剑指offer上的题很多

    - **快速选择算法(Kth Largest Element)**: 选择一个无序数组中的第k大的元素。 #### 二分搜索扩展 - **二分搜索变体(First Position of Target)**: 在排序数组中寻找目标值的第一个位置。 - **查找插入位置(Search...

    java-leetcode题解之Largest Number.java

    java java_leetcode题解之Largest Number.java

    机试高频考点.docx

    【字符串知识】 在编程面试中,字符串是常...例如《合并两个有序数组》(https://leetcode-cn.com/problems/merge-sorted-array/)、《最大数字》(https://leetcode-cn.com/problems/largest-number/)以及《最大间距》...

    扩展矩阵leetcode-Leetcode:LeetcodeAnswer-Java

    扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 maxArea 26.删除排序数组中的重复项 removeDuplicates 33.搜索旋转排序数组 ...34.在排序数组中查找元素的第一个和最后一个...largestNumber 324.摆

    C++-leetcode题解之747. Largest Number At Least Twice of Others.cpp

    c++ C++_leetcode题解之747. Largest Number At Least Twice of Others.cpp

    LeetCode最全代码

    191 |[Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/) | [C++](./C++/number-of-1-bits.cpp) [Python](./Python/number-of-1-bits.py) | _O(1)_ | _O(1)_ | Easy ||| 201 | [Bitwise AND of ...

    leetcode316-LeetCode:leetcode的解决方案

    Largest Rectangle in Histogram:单调栈 Island Perimeter:简单对比(map+zip的使用) or 遍历查找 Max Area of Island:DFS(本来想用DP,发现出不来) Number of Islands:DFS My Calendar II:小空间匹配 My ...

    leetcode寻找最近的-qyhc:群英荟萃,各种资源,欢迎各位大佬共享笔记或资源

    leetcode寻找最近的 设计模式 ...随时随记 随记笔记 ...最大数(golang)](Alg/leetcode/largestNumber.go [190. 颠倒二进制位(golang)](Alg/leetcode/reverseBits.go Docker 面试题 GO面试题 Redis面试题

    Leetcode题目+解析+思路+答案.pdf

    - **Largest Rectangle in Histogram**:在直方图中找到最大的矩形面积。 - **Maximal Rectangle**:在二维矩阵中找到最大的矩形。 - **Palindrome Number**:判断一个数字是否是回文数。 - **Search a 2D ...

    leetcode答案-easy_Maximum-Subarray:easy_Maximum-Subarray

    leetcode 答案 easy_Maximum-Subarray 提交链接 / Submit (You need register/login first before submit.) (在提交前你需要先注册或登录) 题目描述 / Description Given an integer array nums, find the ...

    python-leetcode面试题解之第179题最大数-题解.zip

    print(largestNumber(nums)) # 输出:9534330 ``` 通过这个题目,我们可以深入理解Python的字符串操作、排序功能以及如何自定义排序规则。同时,这也是一个很好的练习,可以帮助开发者提升解决实际问题的能力,尤其...

    leetcode装最多水-Leetcode:解决了leetcode问题

    largest element from an unsorted array in linear time. (1) If the number of elements in an array is large .Divide the array into arrays each with 5 elements. n/5 arrays. (2) Compute Median of these 5 ...

    LeetCode leetcode部分题解答代码实现

    * Largest Rectangle in Histogram:给定一个直方图,返回直方图中的最大矩形面积。这个题目需要使用栈的思想,将直方图中的每个矩形分解成更小的矩形,并找到最大矩形。 * Maximal Rectangle:给定一个矩形,返回...

    lrucacheleetcode-LeetCodeSheet:记录自己Leetcode之旅

    Number Leetcode 75. Sort Colors Leetcode 215. Kth Largest Element Leetcode 4. Median of Two Sorted Arrays 注意:后两题是与快速排序非常相似的快速选择(Quick Select)算法,面试中很常考 链表类(Linked ...

    LeetCode C++全解

    1. Introduction ... Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element

    LeetCode练习答案

    - **直方图中的最大矩形(Largest Rectangle in Histogram)**: 给定直方图的高度,计算能够组成的矩形的最大面积。 - **最大矩形(Maximal Rectangle)**: 在由'0'和'1'组成的二维矩阵中,找到只包含'1'的最大矩形,并...

    gasstationleetcode-LeetCode:Leet和其他OJ问题

    加油站 leetcode 力码 该文件夹不仅包含算法和数据库的leetcode问题,还包含其他公开...largest distance from the sum of any subarray to the average of subarray (sum(a[n])/(k+1)). Output: a number of the Im

    leetcode

    例如,"Kth Largest Element in an Array"可以通过优先队列在O(n log k)的时间复杂度内找到答案。 五、Java特性的运用 Java的一些高级特性如泛型、枚举、接口、匿名内部类、Lambda表达式等也会在解题中发挥重要作用...

Global site tag (gtag.js) - Google Analytics