Space-Filling Curves

wiki：https://en.wikipedia.org/wiki/Space-filling_curve

1.Space-Filling Curve

2.Z-curve

致谢：https://www.docin.com/p-830484046.html

归并排序

    public void merge(int[] a, int low, int mid, int high) {
        int[] b = Arrays.copyOf(a, a.length);
        int i, j, k;
        for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
            if (b[i] < b[j])
                a[k] = b[i++];
            else
                a[k] = b[j++];
        }
        while (i <= mid)
            a[k++] = b[i++];
        while (j <= high)
            a[k++] = b[j++];
    }

    public void mergesort(int[] a, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergesort(a, low, mid);
            mergesort(a, mid + 1, high);
            merge(a, low, mid, high);
        }
    }

public void merge(int[] a, int low, int mid, int high) {

int[] b = Arrays.copyOf(a, a.length);

int i, j, k;

for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {

if (b[i] < b[j])

a[k] = b[i++];

else

a[k] = b[j++];

}

while (i <= mid)

a[k++] = b[i++];

while (j <= high)

a[k++] = b[j++];

}

public void mergesort(int[] a, int low, int high) {

if (low < high) {

int mid = (low + high) / 2;

mergesort(a, low, mid);

mergesort(a, mid + 1, high);

merge(a, low, mid, high);

}

快速排序快排 TOPK

1.TOPK

 public void quicksort(int []a,int low,int high){
        if(low<high){
            int pivot=partition(a,low,high);
            quicksort(a,low,pivot-1);
            quicksort(a,pivot+1,high);
        }
    }
    
    public int partition(int []a,int low,int high){
        int pivot=a[low];
        while(low<high){
            while(low<high && a[high]>=pivot)
                high--;
            a[low]=a[high];
            while(low<high && a[low]<=pivot)
                low++;
        a[high]=a[low];
        }
        a[low]=pivot;
        return low;
    }

public void quicksort(int []a,int low,int high){

if(low<high){

int pivot=partition(a,low,high);

quicksort(a,low,pivot-1);

quicksort(a,pivot+1,high);

}

public int partition(int []a,int low,int high){

int pivot=a[low];

while(low<high){

while(low<high && a[high]>=pivot)

high--;

a[low]=a[high];

while(low<high && a[low]<=pivot)

low++;

a[high]=a[low];

}

a[low]=pivot;

return low;

}

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package gongel_first;

import java.util.PriorityQueue;

public class Twohundred_fifteen {
    /**
     * 快排、快速排序
     */
    public int paritition(int[] nums, int low, int high) {
        int pivot = nums[low];
        while (low < high) {//下面顺序不能交换， 因为pivot首先保存的是low
            while (low < high && nums[high] >= pivot)
                high--;
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot)
                low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length)
            return -1;
        k = nums.length - k;//如果不进行此操作，则是找到数组中第k小的元素;例如4/5/6/7/8,第四大元素对应的下标为5-4=1
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int pivoit_pos = paritition(nums, low, high);
            if (pivoit_pos == k)
                return nums[pivoit_pos];
            else if (pivoit_pos > k)
                high = pivoit_pos - 1;
            else
                low = pivoit_pos + 1;
        }
        return nums[k];
    }

    /**
     * 优先队列实现小根堆
     */
    public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int val : nums) {
            pq.add(val);
            if (pq.size() > k)//相当于nums.length-k；从nums中丢弃前nums.length-(k+1)+1=nums.length-k个最小的元素
                pq.poll();
        }
        return pq.peek();
    }
}

package gongel_first;

import java.util.PriorityQueue;

public class Twohundred_fifteen {

/**

* 快排、快速排序

public int paritition(int[] nums, int low, int high) {

int pivot = nums[low];

while (low < high) {//下面顺序不能交换，因为pivot首先保存的是low

while (low < high && nums[high] >= pivot)

high--;

nums[low] = nums[high];

while (low < high && nums[low] <= pivot)

low++;

nums[high] = nums[low];

}

nums[low] = pivot;

return low;

}

public int findKthLargest(int[] nums, int k) {

if (nums == null || nums.length == 0 || k <= 0 || k > nums.length)

return -1;

k = nums.length - k;//如果不进行此操作，则是找到数组中第k小的元素;例如4/5/6/7/8,第四大元素对应的下标为5-4=1

int low = 0, high = nums.length - 1;

while (low < high) {

int pivoit_pos = paritition(nums, low, high);

if (pivoit_pos == k)

return nums[pivoit_pos];

else if (pivoit_pos > k)

high = pivoit_pos - 1;

else

low = pivoit_pos + 1;

}

return nums[k];

}

/**

* 优先队列实现小根堆

public int findKthLargest2(int[] nums, int k) {

PriorityQueue<Integer> pq = new PriorityQueue<>();

for (int val : nums) {

pq.add(val);

if (pq.size() > k)//相当于nums.length-k；从nums中丢弃前nums.length-(k+1)+1=nums.length-k个最小的元素

pq.poll();

}

return pq.peek();

}

class Solution {
public:
    int findKthLargest(vector<int> &nums, int k) {
        if (nums.size() == 0)
            return -1;
        priority_queue<int, vector<int>, greater<int> > pq;
        for (auto num:nums) {
            pq.push(num);
            if (pq.size() > k)
                pq.pop();
        }
        return pq.top();
    }

    int findKthLargest2(vector<int> &nums, int k) {
        if (nums.size() == 0)
            return -1;
        k = nums.size() - k;
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = paritition(low, high, nums);
            if (pivot == k)
                return nums[k];
            else if (pivot > k)
                high = pivot - 1;
            else
                low = pivot + 1;
        }
        return nums[k];
    }

    int paritition(int low, int high, vector<int> &nums) {
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= pivot)
                high--;
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot)
                low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }
};

class Solution {

public:

int findKthLargest(vector<int> &nums, int k) {

if (nums.size() == 0)

return -1;

priority_queue<int, vector<int>, greater<int> > pq;

for (auto num:nums) {

pq.push(num);

if (pq.size() > k)

pq.pop();

}

return pq.top();

}

int findKthLargest2(vector<int> &nums, int k) {

if (nums.size() == 0)

return -1;

k = nums.size() - k;

int low = 0;

int high = nums.size() - 1;

while (low < high) {

int pivot = paritition(low, high, nums);

if (pivot == k)

return nums[k];

else if (pivot > k)

high = pivot - 1;

else

low = pivot + 1;

}

return nums[k];

}

int paritition(int low, int high, vector<int> &nums) {

int pivot = nums[low];

while (low < high) {

while (low < high && nums[high] >= pivot)

high--;

nums[low] = nums[high];

while (low < high && nums[low] <= pivot)

low++;

nums[high] = nums[low];

}

nums[low] = pivot;

return low;

}

};

2.三路快排

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:

不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]

输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。

首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。

你能想出一个仅使用常数空间的一趟扫描算法吗？

public class Seventy_five {
    /**
     * 三路快排
     */
    public void sortColors(int[] nums) {
        int zero = -1, one = 0, two = nums.length;
        while (one < two) {
            if (nums[one] == 0) {
                swap(nums, ++zero, one++);
            } else if (nums[one] == 2) {
                swap(nums, --two, one);
            } else {
                ++one;
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

public class Seventy_five {

/**

* 三路快排

public void sortColors(int[] nums) {

int zero = -1, one = 0, two = nums.length;

while (one < two) {

if (nums[one] == 0) {

swap(nums, ++zero, one++);

} else if (nums[one] == 2) {

swap(nums, --two, one);

} else {

++one;

}

public void swap(int[] nums, int i, int j) {

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

}

class Solution {
public:
    void sortColors(vector<int> &nums) {
        int zero = -1;
        int one = 0;
        int two = nums.size();
        while (one < two) {
            if (nums[one] == 0) {
                swap(nums,++zero, one++);
            } else if(nums[one]==2){
                swap(nums,--two,one);
            } else{
                one++;
            }
        }
    }

    void swap(vector<int> &nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

class Solution {

public:

void sortColors(vector<int> &nums) {

int zero = -1;

int one = 0;

int two = nums.size();

while (one < two) {

if (nums[one] == 0) {

swap(nums,++zero, one++);

} else if(nums[one]==2){

swap(nums,--two,one);

} else{

one++;

}

void swap(vector<int> &nums, int i, int j) {

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

}

};

FLAG！

算法题一年内至少刷三遍！！！

LeetCode中国官方题库。

Coding Record

厚积薄发！

New Flag(20190828–): 看paper, 7:30左右起床看。

How to Publish Paper ?

研一下课程

这学期基本没课了，不想学习不想做项目不想看论文的时候就去听听课好了。

附上下学期课程：

COMP620021
计算机网络安全技术
54
3
吴承荣
计算机
邯郸校区
1-18周,星期四第6-8节(逸夫楼407室) 
40
 
 
COMP620021
计算机网络安全技术(工研院)
54
3
吴承荣
计算机
邯郸校区
1-18周,星期四第6-8节(逸夫楼407室) 
2
 
 
COMP630022
生物信息学2018201902COMP630022.01
54
3
王飞
计算机
邯郸校区
1-16周,星期五第6-8节(H4406) 
30
 
 
COMP630027
文本挖掘
54
3
朱山风
计算机
邯郸校区
1-18周,星期三第11-13节(逸夫楼605室) 
50
 
 
COMP630027
文本挖掘(工研院)
54
3
朱山风
计算机
邯郸校区
1-18周,星期三第11-13节(逸夫楼605室) 
5
 
 
COMP630053
半结构与非结构数据管理与分析
54
3
周向东 谈子敬
计算机
邯郸校区
1-18周,星期二第6-8节(逸夫楼510室) 
10
 
 
COMP630064
大数据安全
54
3
曾剑平
计算机
邯郸校区
1-18周,星期五第2-4节(逸夫楼605室) 
40
 
 
COMP630064
大数据安全(工研院)
54
3
曾剑平
计算机
邯郸校区
1-18周,星期五第2-4节(逸夫楼605室) 
2
 
 
COMP630066
领域数据学
54
3
池明旻
计算机
邯郸校区
1-18周,星期一第11-13节(H4104) 
10
 
 
COMP630073
面向大数据的机器学习理论与算法(工研院)
54
3
张军平
计算机
邯郸校区
1-18周,星期一第6-8节(HGX506) 
8
 
 
COMP620042
语音和语言信息处理(工研院)
54
3
黄萱菁
计算机
张江校区
1-18周,星期四第6-8节(Z2310A) 
12
 
 
COMP620043
数字视频处理(工研院)
54
3
颜波
计算机
张江校区
1-18周,星期二第2-4节(Z2103) 
7
 
 
COMP620045
计算机视觉(工研院)
54
3
陈雁秋
计算机
张江校区
1-18周,星期三第6-8节(Z2307A) 
21
 
 
COMP620052
并发理论
54
3
张亮
计算机
张江校区
1-18周,星期三第6-8节(Z2206) 
20
 
 
COMP620052
并发理论(工研院)
54
3
张亮
计算机
张江校区
1-18周,星期三第6-8节(Z2206) 
2
 
 
COMP630028
服务计算
54
3
张亮
计算机
张江校区
1-18周,星期三第2-4节(Z2203) 
2
 
 
COMP630065
大数据前沿技术2018201902COMP630065.01
54
3
肖仰华 汪卫
计算机
张江校区
1-16周,星期四第11-13节(Z2209A) 
70
 
 
COMP630065
大数据前沿技术(工研院)
54
3
肖仰华 汪卫
计算机
张江校区
1-18周,星期四第11-13节(Z2209A) 
2
 
 
COMP630072
多模态跨媒体信息处理2018201902COMP630072.01
54
3
张玥杰
计算机
张江校区
1-16周,星期二第2-4节(Z2206) 
30
 
 
COMP620002
人工智能2018201902COMP620002.01
54
3
危辉
计算机
 
1-16周,星期一第2-4节(Z2310A) 
70
 
 
COMP620006
算法续论2018201902COMP620006.01
54
3
沙朝锋
计算机
 
1-16周,星期五第6-8节(H6507) 
40
 
 
COMP620018
分布式数据库2018201902COMP620018.01
54
3
卢暾
计算机
 
1-16周,星期三第2-4节(Z2303) 
40
 
 
COMP620041
移动计算2018201902COMP620041.01
54
3
陈阳 王新
计算机
 
1-16周,星期三第11-13节(Z2311) 
30
 
 
COMP620042
语音和语言信息处理2018201902COMP620042.01
54
3
黄萱菁
计算机
 
1-16周,星期四第6-8节(Z2310A) 
50
 
 
COMP620043
数字视频处理2018201902COMP620043.01
54
3
颜波
计算机
 
1-16周,星期二第2-4节(Z2103) 
40
 
 
COMP620045
计算机视觉2018201902COMP620045.01
54
3
陈雁秋
计算机
 
1-16周,星期三第6-8节(Z2307A) 
40
 
 
COMP620049
大数据的支撑平台2018201902COMP620049.01
54
3
王鹏
计算机
 
1-16周,星期二第1-3节(Z2307A) 
50
 
 
COMP620054
计算智能2018201902COMP620054.01
54
3
郭跃飞
计算机
 
1-16周,星期四第6-8节(H3408) 
40
 
 
COMP630028
服务计算2018201902COMP630028.01
54
3
张亮
计算机
 
1-16周,星期三第2-4节(Z2203) 
30
 
 
COMP630038
机器人学导论2018201902COMP630038.01
54
3
张文强
计算机
 
1-16周,星期五第6-8节(Z2307A) 
60
 
 
COMP630040
数据库新进展2018201902COMP630040.01
54
3
王轶彤 王智慧
计算机
 
1-16周,星期一第6-8节(Z2312) 
40
 
 
COMP630047
多媒体信息隐藏和水印技术2018201902COMP630047.01
54
3
李伟
计算机
 
1-16周,星期四第6-8节(Z2307A) 
20
 
 
COMP630073
面向大数据的机器学习理论与算法2018201902COMP630073.01
54
3
张军平
计算机
 
1-16周,星期一第6-8节(HGX506) 
60
 
 
COMP630074
互联网应用新进展2018201902COMP630074.01
54
3
赵进
计算机
 
1-16周,星期二第6-8节(Z2203) 
40
 
 
COMP630074
互联网应用新进展
54
3
赵进
计算机
 
1-18周,星期二第6-8节(Z2203) 
5

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

COMP620021

计算机网络安全技术

吴承荣

计算机

邯郸校区

1-18周,星期四第6-8节(逸夫楼407室)

COMP620021

计算机网络安全技术(工研院)

吴承荣

计算机

邯郸校区

1-18周,星期四第6-8节(逸夫楼407室)

COMP630022

生物信息学2018201902COMP630022.01

王飞

计算机

邯郸校区

1-16周,星期五第6-8节(H4406)

COMP630027

文本挖掘

朱山风

计算机

邯郸校区

1-18周,星期三第11-13节(逸夫楼605室)

COMP630027

文本挖掘(工研院)

朱山风

计算机

邯郸校区

1-18周,星期三第11-13节(逸夫楼605室)

COMP630053

半结构与非结构数据管理与分析

周向东谈子敬

计算机

邯郸校区

1-18周,星期二第6-8节(逸夫楼510室)

COMP630064

大数据安全

曾剑平

计算机

邯郸校区

1-18周,星期五第2-4节(逸夫楼605室)

COMP630064

大数据安全(工研院)

曾剑平

计算机

邯郸校区

1-18周,星期五第2-4节(逸夫楼605室)

COMP630066

领域数据学

池明旻

计算机

邯郸校区

1-18周,星期一第11-13节(H4104)

COMP630073

面向大数据的机器学习理论与算法(工研院)

张军平

计算机

邯郸校区

1-18周,星期一第6-8节(HGX506)

COMP620042

语音和语言信息处理(工研院)

黄萱菁

计算机

张江校区

1-18周,星期四第6-8节(Z2310A)

COMP620043

数字视频处理(工研院)

颜波

计算机

张江校区

1-18周,星期二第2-4节(Z2103)

COMP620045

计算机视觉(工研院)

陈雁秋

计算机

张江校区

1-18周,星期三第6-8节(Z2307A)

COMP620052

并发理论

张亮

计算机

张江校区

1-18周,星期三第6-8节(Z2206)

COMP620052

并发理论(工研院)

张亮

计算机

张江校区

1-18周,星期三第6-8节(Z2206)

COMP630028

服务计算

张亮

计算机

张江校区

1-18周,星期三第2-4节(Z2203)

COMP630065

大数据前沿技术2018201902COMP630065.01

肖仰华汪卫

计算机

张江校区

1-16周,星期四第11-13节(Z2209A)

COMP630065

大数据前沿技术(工研院)

肖仰华汪卫

计算机

张江校区

1-18周,星期四第11-13节(Z2209A)

COMP630072

多模态跨媒体信息处理2018201902COMP630072.01

张玥杰

计算机

张江校区

1-16周,星期二第2-4节(Z2206)

COMP620002

人工智能2018201902COMP620002.01

危辉

计算机

1-16周,星期一第2-4节(Z2310A)

COMP620006

算法续论2018201902COMP620006.01

沙朝锋

计算机

1-16周,星期五第6-8节(H6507)

COMP620018

分布式数据库2018201902COMP620018.01

卢暾

计算机

1-16周,星期三第2-4节(Z2303)

COMP620041

移动计算2018201902COMP620041.01

陈阳王新

计算机

1-16周,星期三第11-13节(Z2311)

COMP620042

语音和语言信息处理2018201902COMP620042.01

黄萱菁

计算机

1-16周,星期四第6-8节(Z2310A)

COMP620043

数字视频处理2018201902COMP620043.01

颜波

计算机

1-16周,星期二第2-4节(Z2103)

COMP620045

计算机视觉2018201902COMP620045.01

陈雁秋

计算机

1-16周,星期三第6-8节(Z2307A)

COMP620049

大数据的支撑平台2018201902COMP620049.01

王鹏

计算机

1-16周,星期二第1-3节(Z2307A)

COMP620054

计算智能2018201902COMP620054.01

郭跃飞

计算机

1-16周,星期四第6-8节(H3408)

COMP630028

服务计算2018201902COMP630028.01

张亮

计算机

1-16周,星期三第2-4节(Z2203)

COMP630038

机器人学导论2018201902COMP630038.01

张文强

计算机

1-16周,星期五第6-8节(Z2307A)

COMP630040

数据库新进展2018201902COMP630040.01

王轶彤王智慧

计算机

1-16周,星期一第6-8节(Z2312)

COMP630047

多媒体信息隐藏和水印技术2018201902COMP630047.01

李伟

计算机

1-16周,星期四第6-8节(Z2307A)

COMP630073

面向大数据的机器学习理论与算法2018201902COMP630073.01

张军平

计算机

1-16周,星期一第6-8节(HGX506)

COMP630074

互联网应用新进展2018201902COMP630074.01

赵进

计算机

1-16周,星期二第6-8节(Z2203)

COMP630074

互联网应用新进展

赵进

计算机

1-18周,星期二第6-8节(Z2203)

2019年二月
一	二	三	四	五	六	日
« 1月				3月 »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28