【Leetcode】Count of Smaller Numbers After Self
发布时间：2020-12-13 21:08:12 所属栏目：PHP教程 来源：网络整理
导读：题目链接：https://leetcode.com/problems/count-of-smaller-numbers-after-self/ 题目： You are given an integer arraynumsand you have to return a newcountsarray. Thecountsarray has the property where counts[i] is the number of smaller element
|
题目链接：https://leetcode.com/problems/count-of-smaller-numbers-after-self/ 题目：
You are given an integer array nums and you have to return a new counts array. The counts array has the property where Example: Given nums = [5,2,6,1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array 思路： 建立1个2叉搜索树，在建树的进程中，记录在数组右侧比本身小的元素个数。 算法复杂度O(nlogn)，用动态计划复杂度为O(n^2)。
其中cnt为该结点相同大小元素的个数，用于重复元素判断。。。其实可以省略。。懒得改了 算法： public List<Integer> countSmaller(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
int res[] = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
res[i] = insert(nums[i]);
}
for (int i : res) {
list.add(i);
}
return list;
}
TreeNode tRoot;
private Integer insert(int val) {
int cnt = 0;
if (tRoot == null) {
tRoot = new TreeNode(val);
return cnt;
}
TreeNode root = tRoot;
while (root != null) {
if (val < root.val) {
root.leftCnt++;
if (root.left == null) {
root.left = new TreeNode(val);
break;
} else
root = root.left;
} else if (val > root.val) {
cnt += root.leftCnt + root.cnt;
if (root.right == null) {
root.right = new TreeNode(val);
break;
} else
root = root.right;
} else {
cnt += root.leftCnt;
root.cnt++;
break;
}
}
return cnt;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |