5 优化时间和空间效率

题目描述

数组中有⼀个数字出现的次数超过数组长度的⼀半，请找出这个数字。例如输⼊⼀个长度为9的数组 {1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的⼀半，因此输出2。

解题思路

题目描述

输⼊ $n$ 个整数，找出其中最⼩的 $k$ 个数。例如输⼊4、 5、1、6、2、7、3、8这8个数字，则最⼩的4个数字是1、2、3、 4。

解题思路

题目描述

输⼊⼀个整型数组，数组⾥有正数也有负数。数组中⼀个或连续的多个整数组成⼀个⼦数组。求所有⼦数组的和的最⼤值。要求时间复杂度为 $O(n)$ 。

解题思路

题目描述

输⼊⼀个整数 $n$ ，求从1到 $n$ 这 $n$ 个整数的⼗进制表⽰中1出现的次数。例如输⼊12，从1到12这些整数中包含1的数字有1，10，11和12，1⼀共出现了5次。

解题思路

题目描述

题⽬：输⼊⼀个正整数数组，把数组⾥所有数字拼接起来排成⼀个数，打印能拼接出的所有数字中最⼩的⼀个。例如输⼊数组{3, 32, 321}，则打印出这3个数字能排成的最⼩数字321323。

解题思路

与179. Largest Number类似，只不过把最大改成了最小。

题目描述

题⽬：我们把只包含因⼦2、3和5的数称作丑数（Ugly Number）。求按从⼩到⼤的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因⼦7。习惯上我们把1当做第⼀个丑数。

解题思路

题目描述

在字符串中找出第⼀个只出现⼀次的字符。如输⼊"abaccdeff"，则输出'b'。

解题思路

题目描述

在数组中的两个数字如果前⾯⼀个数字⼤于后⾯的数字，则这两个数字组成⼀个逆序对。输⼊⼀个数组，求出这个数组中的逆序对的总数。

解题思路

题目描述

输⼊两个链表，找出它们的第⼀个公共结点。

解题思路